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

Junu Kim·2025년 12월 23일

Java baekjoon boj

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

64/89

[2231] 분해합

난이도: ★☆☆☆☆ • solved on: 2025-12-23

문제 요약

문제 유형: 완전탐색(브루트포스), 구현
요구사항: 주어진 자연수 N에 대해, N = i + (i의 각 자리수 합)을 만족하는 가장 작은 생성자 i를 찾아 출력해야 한다. 없으면 0을 출력한다.

사용 개념

자료구조
- 없음 (기본 변수만 사용)
알고리즘/기법
- 완전탐색 (Brute Force)
- 탐색 시작점 최적화: N - 9 * (자릿수)부터 검사
핵심 키워드
- 분해합 (decomposition sum)
- 생성자 (generator)
- 자릿수 합 (digit sum)

풀이 아이디어

문제 분해

어떤 수 i의 분해합은 i + (자리수 합)이다.

자리수 합의 최댓값은 (자릿수 L일 때) 9L이므로,

i가 생성자라면 i >= N - 9L 범위 안에 있어야 한다.

따라서 N - 9L부터 N-1까지 후보만 검사하면 된다.
핵심 로직 흐름
start = N - 9 * len(N)
for i from start to N-1:
    total = i + sumDigits(i)
    if total == N:
        print i
        종료
print 0
예외 처리

생성자가 없는 경우 → 0 출력

시작점이 음수가 될 수 있음(예: N이 매우 작을 때)

현재 코드도 동작은 하며(음수 후보는 어차피 불일치), 일반적으로는 max(1, start)로 보정하기도 함.

코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String candidate;
        long total = 0;
        long n = Long.parseLong(s);
        int digit;

        for (long i = n - 9*s.length(); i < n; i++) {
            candidate = String.valueOf(i);
            for(int j = 0; j < candidate.length(); j++) {
                digit = candidate.charAt(candidate.length() - j - 1) - '0';
                total += digit;
            }
            total += i;
            if(total == n){
                System.out.println(i);
                return;
            }
            total = 0;
        }
        System.out.println(0);
    }
}