2231문제 분해합(완전탐색,브루트포스) Java

https://www.acmicpc.net/problem/2231

2231번: 분해합

 

매우 비효율적으로 완전탐색을 진행함…;;

결국 분해합이 나오는 공식의 경우

아래가 포인트

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;                

}



}