[JAVA] 백준 2231번 - 분해합

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

2231번: 분해합

 

 

 

분해합은 해당 (자연수 + 자연수의 각 자리 수 합) 이다.

자연수 m의 분해합이 n인 경우 m을 n의 생성자라 한다.

 

예를 들어, 198의 분해합은 (198+1+9+8) = 216 이다.

198은 216의 생성자이다. 

 

자연수 n의 가장 작은 생성자를 찾는 문제이다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int m=0;
        int sum=0;

        for(int i=0; i<n; i++){ // 생성자의 경우의 수를 0부터 n까지 탐색
            m = i;
            sum = i;

            while (m > 0) { // 각 자리수 더한 값 구하기
                int num = m % 10;
                sum += num;
                m /= 10;
            }
            if(sum == n) { // 각 자리수 더한 값이 n과 같으면
                System.out.println(i); // 생성자이므로 출력
                return;
            }
        }
        System.out.println(0);
    }
}

 

 

0부터 n까지 모든 경우의 수를 탐색해 생성자가 될 수 있는 수를 찾는다.

각 자리 수 더한 값이 n과 같아지는 첫 순간이 최소 생성자이므로 바로 출력한다.