[백준] 2231:분해합 (자바)

---

package buffer;

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int length = String.valueOf(N).length();
        int i = 0;

        for(i = Math.max(N - length*9, 0); i < N; i++) {
            int sum = 0;
            String num = String.valueOf(i);
            for(int j = 0; j < num.length(); j++) {
                sum += Integer.parseInt(String.valueOf(num.charAt(j)));
            }
            sum += i;
            if(N == sum) break;
        }

        System.out.println(i==N?0:i);
    }
}

처음에는 0부터 N까지 반복하면서 찾아야 하나 생각이 들었다.
그럼 너무 비효율적일 것 같아서 반복 횟수를 줄이는 방법을 생각해냈다.

N이 999라고 한다면, 생성자는 무조건 세 자리수 이하일 것이다.
생성자 자기 자신 + 각 자리 수의 합이 999가 되어야 한다.
각 자리수의 합은 최대값은 9*3 인 27이 된다.
(1~27) + x = 999, => 즉 972 <= x <= 998 을 가진다.
때문에 N 값에서 각 자리수 합의 최대값을 뺀 값까지만 탐색하면 된다는 판단을 내렸다.

가장 작은 생성자를 찾는 것이기 때문에, 생성자가 될 수 있는 N - (N의 최대 자리수 합) 부터 i를 반복하고 생성자를 찾을 시 종료해주면 된다.

만약 N이 한 자리수라면 i의 시작 값이 음수가 되기 때문에 예외가 발생한다.
이를 Math.max(i값, 0) 으로 처리해주면서 예외를 없애주었다.