[백준] 12348번 - 분해합 2 [Java]

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

 

[백준] 12348번 - 분해합 2 [Java]

---

1.  아이디어

 

이전 분해합 문제에서 N의 범위가 훨씬 커진 문제로 1부터 N까지 모든 수를 탐색하기엔 너무 많은 시간이 걸린다. 분해합은 해당 숫자와 각 자리수의 합이므로 역으로 해당 숫자의 길이를 통해 분해합을 구할 숫자의 범위를 줄이는 방식으로 해결할 수 있다. 길이 L인 숫자 N의 생성자는 N보다 작은 수여야 하며 길이도 최대 L이다. 각 자리수의 최대값은 9이므로 역으로 N의 생성자의 최소값은 N - 9 * L 부터 가능함을 알 수 있다.

---

2. 문제풀이

 

이전 분해합 문제에서 타입들을 long으로 바꾸고 탐색 범위를 바꿔주는 방식으로 구현했다.

---

3. 코드

 

import java.io.*;

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

        String input = br.readLine();
        long len = input.length();

        long N = Long.parseLong(input);
        long ans = 0;

        for (long i = N - 9 * len; i <= N; i++) {
            long sum = solve(i);

            if (sum == N) {
                ans = i;
                break;
            }
        }

        System.out.println(ans);
    }

    private static long solve(long N) {
        long sum = N;

        while (N != 0) {
            sum += N % 10;
            N /= 10;
        }

        return sum;
    }

}

---

4. 후기