백준 2231번 [분해합](C++)-yes6686- 티스토리

백준 문제 풀이: 2231 [분해합]

---

문제 링크: https://www.acmicpc.net/problem/2231

문제 설명:

어떤 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 찾는 문제입니다.

• 생성자는 자연수 M과 각 자리 숫자의 합을 더한 값이 N이 되는 M을 의미합니다.
• 예를 들어, N = 256인 경우, 생성자 M은 245입니다. 245 + 2 + 4 + 5 = 256

생성자가 없으면 0을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        int sum = i;
        int temp = i;

        // 각 자리 숫자의 합을 구함
        while (temp > 0) {
            sum += temp % 10;
            temp /= 10;
        }

        // 생성자를 찾은 경우 출력 후 종료
        if (sum == n) {
            cout << i << '\n';
            return 0;
        }
    }

    // 생성자가 없는 경우
    cout << 0 << '\n';
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 1부터 N까지 모든 숫자를 탐색하여 생성자인지 확인합니다.
• 구현 세부사항:
  • 각 숫자의 자리수 합을 계산하고 원래 숫자와 더한 결과가 N과 같은지 확인합니다.
  • 처음으로 조건을 만족하는 숫자를 출력하고 프로그램을 종료합니다.
  • 모든 숫자를 확인했음에도 생성자가 없으면 0을 출력합니다.
• 시간 복잡도: O(n ⋅ d), 여기서 d는 숫자의 자릿수입니다.
  • 최대 자릿수는 log(n)에 비례하므로 효율적입니다.

---

결과

주어진 N에 대한 가장 작은 생성자를 출력하거나, 생성자가 없으면 0을 출력합니다. 모든 숫자를 탐색하는 단순한 완전 탐색 알고리즘을 사용해 문제를 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!