[BaekJoon] 2231번 - 분해합 [Java][C++]

문제 링크

---

1. 문제 풀이

자연수 $N$ 에 대한 가장 작은 생성자를 구하는 문제로 생성자는 해당 숫자와 각 자릿수의 합이 $N$ 이 되는 수들이다. $1$ 부터 $N$ 까지 모든 자연수에 대해 순서대로 분해합을 구해서 $N$ 이 되는지 비교해보면 해결할 수 있다. 자연수 $N$ 의 생성자는 자기 자신과 각 자릿수의 합으로 이루어져서 항상 $N$ 보다 작다.

각 자릿수는 해당 숫자를 $10$ 으로 나눈 나머지를 더하고 해당 숫자를 $10$ 으로 나눈 몫만 취하는 과정을 반복하면 구할 수 있다.

---

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));

        int N = Integer.parseInt(br.readLine());
        for (int i = 1; i <= N; i++) {
            int num = i;
            int 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(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        int x = i;
        int sum = x;
        while (x > 0) {
            sum += x % 10;
            x /= 10;
        }

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

    cout << 0;
}

---