분해합 (Decomposition Sum)

 

정의

어떤 자연수 N에 대해, 자기 자신과 각 자리수의 합을 더한 값

어떤 수 x의 분해합을 d(x)라고 하면 다음과 같이 정의합니다.

d(x) = x + (x의 각 자리수의 합)

예) x = 245 → 자리수 합 = 2+4+5=11 → d(245) = 245+11 = 256

핵심 메시지

분해합 문제의 목표는 보통 “주어진 N의 생성자(constructor) x를 찾는 것”입니다.

즉, d(x) = N을 만족하는 가장 작은 x를 찾거나, 없으면 0을 출력합니다.

 

수학 개념

생성자(Generator)와 탐색 범위 줄이기

생성자란?

어떤 자연수 N에 대해 d(x) = N을 만족하는 x를 N의 생성자라고 합니다.

생성자는 여러 개일 수 있으며, 코딩테스트에서는 보통 가장 작은 생성자를 요구합니다.

탐색 시작점을 줄이는 이유

각 자릿수가 가질 수 있는 가장 큰 숫자는 9이기 때문에, x의 자릿수를 d라고 할 때 자리수 합의 최댓값은 9×d입니다.

예를 들어 x가 3자리 수라면, 자릿수 합의 최댓값은 9+9+9 = 27입니다.

d(x) = x + digitSum(x) ≤ x + 9 × d

즉, N의 생성자 x는 최소한 N - 9×d 이상에서만 나타날 수 있습니다.

이 간단한 상한이 “브루트포스지만 충분히 빠르게” 만드는 핵심입니다.

항목	의미	활용
분해합	d(x) = x+자리수합	생성자 판정
생성자	d(x) = N을 만족하는 x	최소 생성자 찾기
9 X 자릿수	자리수합의 최댓값	탐색 시작점 하한

 

알고리즘 개념

분해합 문제는 “범위가 줄어든 완전탐색”이다

풀이 단계

1

탐색 시작점 계산
start = max(1, N - 9×digits(N))

2

후보 x를 순회
x를 start부터 N까지 증가시키며 d(x)를 계산

3

최초로 성립하는 x 반환
d(x)==N이면 x가 최소 생성자이므로 즉시 종료

💡 시간복잡도는 대략 O(9×digits(N) × digits(N)) 입니다.

실제로는 “최대 수십만 ~ 수백만” 범위에서도 충분히 통과하는 경우가 많습니다.

 

구현

Java로 구현하였습니다.

TIP

start = N - 9×digits(N) 를 잡으면 탐색 범위를 크게 줄일 수 있습니다. (자리수합의 최대가 9×digits 이기 때문)

import java.io.*;

public class DecompositionSum {

    static int digitSum(int x) {
        int sum = 0;
        while (x > 0) {
            sum += (x % 10);
            x /= 10;
        }
        return sum;
    }

    static int digits(int n) {
        // n은 자연수라고 가정 (문제 조건에 맞춰 조정)
        return String.valueOf(n).length();
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());

        int d = digits(N);
        int start = Math.max(1, N - 9 * d);

        int answer = 0; // 생성자가 없으면 0
        for (int x = start; x <= N; x++) {
            int value = x + digitSum(x); // d(x)
            if (value == N) {
                answer = x; // 최소 생성자
                break;
            }
        }

        System.out.println(answer);
    }
}

 

예시

N = 256일 때, 왜 생성자는 245인가

245의 자리수 합은 2+4+5=11이고, 분해합은 245+11=256이므로 245는 256의 생성자입니다.

검증

d(245) = 245 + (2 + 4 + 5) = 245 + 11 = 256

 

요약

체크리스트로 마무리

CHECK

✅ 분해합: d(x)=x+자리수합

✅ 생성자: d(x)=N을 만족하는 x

✅ 범위 줄이기: x ≥ N - 9×digits(N)

✅ 풀이 전략: “범위가 줄어든 완전탐색” + 첫 해답에서 종료

✅ 출력: 최소 생성자, 없으면 0