[백준] 분해합

분해합 문제 해결

분해합은 어떤 자연수 N과 그 수를 이루는 각 자리수의 합을 의미합니다. 이 문제에서는 주어진 자연수 N의 가장 작은 생성자를 찾는 것이 목표입니다. 생성자란 어떤 수 M의 분해합으로 N을 만들 수 있는 수를 말합니다.

문제 조건

• 시간 제한: 2초
• 메모리 제한: 192MB
• 제출: 154865
• 정답: 71521
• 맞힌 사람: 56242
• 정답 비율: 45.330%
• 문제링크

2231번: 분해합

입력

• 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어집니다.

출력

• N의 가장 작은 생성자를 출력합니다. 생성자가 없는 경우에는 0을 출력합니다.

주요 개념

• 분해합 계산: 주어진 수의 분해합을 계산하는 함수를 구현합니다.
• 생성자 탐색: 가능한 모든 수를 대상으로 분해합을 계산하고, 주어진 N과 일치할 때 그 수를 출력합니다.

코드 설명

import java.util.Scanner;

public class Main {
    // 주어진 seed로부터 분해합을 생성하는 함수
    public static int generate(int seed) {
        int generatedNumber = seed;
        while (seed > 0) {
            generatedNumber += seed % 10; // 현재 자리의 숫자를 더함
            seed /= 10; // 다음 자리 숫자로 이동
        }
        return generatedNumber; // 계산된 분해합 반환
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 분해합의 대상이 되는 수 N 입력
        int ans = 0;
        // 1부터 N까지 모든 수에 대해 분해합을 계산
        for (int i = 1; i <= N; i++) {
            if (generate(i) == N) { // 분해합이 N과 일치하는 경우
                ans = i; // 생성자를 찾았으므로 저장
                break; // 더 이상의 탐색은 필요 없으므로 반복문 탈출
            }
        }

        System.out.println(ans); // 가장 작은 생성자 출력, 없으면 0 출력
    }
}