[BaekJoon] 12348번 - 분해합 2 [Java][C++]

문제 링크

---

1. 문제 풀이

BaekJoon 2231번 - 분해합 문제에서 $N$ 의 범위가 매우 커진 문제로 이전처럼 $1$ 부터 탐색하는 방식으로는 해결할 수 없다. 분해합은 생성자와 생성자의 각 자릿수의 합으로 구하는데 이때 각 자릿수는 최대 $9$ 까지만 가능하므로 생성자는 분해합에서 $분해합의 길이 - 9$ 보다는 크거나 같다는 것을 알 수 있다. 이를 통해 탐색 범위를 줄여서 브루트 포스로 찾으면 구할 수 있다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;

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

        String str = br.readLine();
        int len = str.length();

        long n = Long.parseLong(str);
        for (long i = n - 9 * len; i <= n; i++) {
            long num = i;
            long sum = num;
            while (num > 0) {
                sum += num % 10;
                num /= 10;
            }

            if (sum == n) {
                System.out.println(i);
                return;
            }
        }

        System.out.println(0);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s;
    cin >> s;

    int len = s.size();

    long long n = stoll(s);
    for (long long i = n - 9 * len; i <= n; i++) {
        long long x = i;
        long long sum = x;
        while (x > 0) {
            sum += x % 10;
            x /= 10;
        }

        if (sum == n) {
            cout << i;
            return 0;
        }
    }

    cout << 0;
}

---