[BOJ 2231] 분해합 - 브루트포스 알고리즘

[BOJ 2231] 분해합 - 브루트포스 알고리즘

문제 링크

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

문제 요약

어떤 자연수 $N$의 분해합은 $N$과 $N$을 이루는 각 자릿수의 합을 의미한다. 자연수 $N$이 주어졌을 때, $N$의 가장 작은 생성자(분해합이 $N$이 되는 수)를 구해내는 프로그램을 작성하시오.

접근 방법

• 자료구조: int (입력값 $N$이 최대 1,000,000이므로 정수형으로 충분함)
• 알고리즘: 브루트포스 (Brute-force)
• 핵심 아이디어: - 생성자 $M$은 항상 $N$보다 작다.
  • 1부터 $N$까지 모든 수를 순회하며 각 수의 분해합을 계산한다.
  • 처음으로 분해합이 $N$과 일치하는 수를 발견하면, 그것이 가장 작은 생성자이므로 출력 후 종료한다.
  • $N$까지 탐색했음에도 발견하지 못하면 0을 출력한다.

풀이 코드

#include <iostream>

using namespace std;

/**
 * 백준 2231번: 분해합
 * 알고리즘: 브루트포스
 */
int main() {
    // 입출력 속도 향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    int result = 0;

    // 1부터 N까지 순차적으로 탐색하여 가장 작은 생성자를 찾음
    for (int i = 1; i < N; i++) {
        int sum = i;    // 현재 숫자 i
        int temp = i;

        // 각 자릿수의 합을 계산
        while (temp > 0) {
            sum += temp % 10; // 1의 자릿수 더하기
            temp /= 10;       // 1의 자릿수 제거
        }

        // 계산된 분해합이 입력받은 N과 같다면 i는 N의 생성자
        if (sum == N) {
            result = i;
            break; // 가장 작은 생성자를 찾아야 하므로 발견 즉시 탈출
        }
    }

    // 결과 출력 (생성자가 없으면 초기값 0이 출력됨)
    cout << result << "\n";

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: $O(N \cdot K)$
• ($N$은 최대 1,000,000, $K$는 자릿수이다. $N$의 범위 내에서 $K$는 최대 7이므로 시간 내 충분히 통과 가능하다.)
• 공간 복잡도: $O(1)$
• (입력값과 계산을 위한 변수 외에 별도의 배열이나 자료구조를 사용하지 않는다.)

실행 결과

• 메모리: 2020 KB
• 시간: 0 ms (또는 탐색량에 따라 4 ms 내외)

핵심 포인트

1. 완전 탐색: $N$의 범위가 100만으로 비교적 작기 때문에 모든 경우를 다 조사해도 시간 초과가 나지 않는다.
2. 자릿수 추출: % 10과 / 10 연산을 반복하여 각 자릿수를 더하는 로직은 코딩테스트에서 매우 자주 쓰이는 패턴이다.
3. 조기 종료: '가장 작은' 것을 찾는 문제이므로 오름차순 탐색 중 조건 만족 시 바로 break를 하는 것이 효율적이다.

예제 확인

• 예제 1: 216 입력 시
  • $i = 198$일 때: $198 + 1 + 9 + 8 = 216$ 성립.
  • 1부터 순차 탐색하므로 198이 가장 먼저 발견됨.
  • 출력: 198