백준 2231 분해합 Java

단계별로 풀어보기 -> 브루트 포스에서 만난 문제인 분해합이다.

나한테는 문제 자체를 이해하기 힘든 문제였다.. 

많은 시간의 고민끝에 이해한 것을 정리하자면

분해합은 숫자 N과 각 자리수의 합을 의미하고

생성자는 그 N을 분해합으로 만들 수 있는 수들을 의미한다. 

245가 있다면 245의 분해합은 245+2+4+5 = 256

256의 생성자는 245인 것이다.

문제는 N이 주어졌을 때 가장 작은 생성자를 출력하는 문제이다.

내가 이해하기 어려웠던 것은

분해합들을 생성자라고 이해하고

예제의 216의 분해합은 216+2+1+6 인데 왜 198 출력이지.. 하고 한참을 미궁에 빠졌었다.

다시 한번 말해서 문제의 요지는

입력받은 N을 분해합으로 만들 수 있는 가장 작은 수를 출력하면 되는 것이다.

브루트 포스 단계에 있는 문제인 만큼 해결 방법 역시

작은 수 부터 가능한 수를 다 분해합 해보면 된다.

N의 범위는 1~1,000,000이다.

하지만 N의 범위만큼 다 분해합해볼 필요는 없다. 다 해보는 코드도 통과가 될지는 모르겠다.

분해합으로 N을 만들 수 있는 범위를 생각해보면 

분해합은 N과 각 자릿수 값의 합이므로 최솟값은 역으로 N에서 더할 수 있는 최대의 자릿수 값들을 빼주면 된다.

각 자리수의 최댓값은 9이므로 9에 자릿수를 곱해서 빼주는 것으로 최솟값을 구할 수 있다.

최댓값은 N이다 분해합으로 N을 만들고자 할 때 N보다 큰 값은 절대 분해합으로 N을 만들 수 없다.

216의 경우엔 세 자리 수 이므로 9 * 3 = 27

216 - 27 = 189가 최솟값이 된다.

더할 수 있는 각 자리수들의 제일 큰 값인 9를 자릿수만큼 빼줬기 때문에

189보다 작은 값들은 분해합으로 절대 N을 만들 수 없는 것이다.

이제는 for문으로 최솟값부터 최댓값까지 모든 경우를 분해합을 만들어보고

N과 일치하면 그 수를 출력하면 된다.

생성자가 없으면 0을 출력하라는 문장은

정답을 저장할 변수의 초기값을 0으로 지정해주면

N과 일치하는 수가 없으면 알아서 0을 출력해주게 된다.

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    int size = String.valueOf(n).length(); // n의 자리수 구하기
    int start = n - (9 * size); // 시작 최솟값 구하기
    int ans = 0;
        
    for(int i = start; i < n; i++) {
        int sum = i; // 합
        int k = i; // 한 자리씩 구하기 우ㅣ함
        while(k > 0) {
            sum += k % 10;
            k /= 10;
        }
        if(sum == n) {
            ans = i;
            break;
        }
    }
    System.out.println(ans);
}

간단하고 이해할 때는 쉬웠는데 내가 부족해서 글로 쓰자니 참 설명하기가 힘든 것 같다.