알고리즘/백준
2231문제 분해합(완전탐색,브루트포스) Java
뭘하지
2021. 9. 17. 10:57
반응형
https://www.acmicpc.net/problem/2231
2231번: 분해합
어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이
www.acmicpc.net
매우 비효율적으로 완전탐색을 진행함…;;
결국 분해합이 나오는 공식의 경우
아래가 포인트
N = M+M첫자리+M두번째자리+M세번째자리 가 바로 생성자.
작은수를 구하는것이기 때문에 N번까지만 반복하면된다.
public class boj_2231 {
public static void main(String[] args) {
int result = 0;
//자연수 N이 주어진다
int N = 216; // 216+2+1+6 = 225
//216 = N+N첫자리+N두번째자리+N세번째자리 생성자.
//N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다.
//N(1 ≤ N ≤ 1,000,000)이 주어진다.
//for(int i=1; i<1000000; i++) {
for(int i=1; i<N; i++) {
if(i+change(i)==N) {
if(result==0) {
result=i;
}else {
result = Math.min(result, i);
}
}
}
System.out.println(result);
}
public static int change(int number) {
String strNumber = Integer.toString(number);
int sum =0;
for(int i=0; i<strNumber.length(); i++) {
sum+=(strNumber.charAt(i)-'0');
}
return sum;
}
}반응형