백준 2231 브루트 포스 분해합 풀이

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

 

나의 풀이

 먼저 생성자와 분해합의 관계성을 고민해보았는데, 생성자에서 분해합으로의 규칙성은 보이는데 분해합에서 생성자로의 규칙성은 잘 보이지가 않는다... 결과적으로 반복문을 사용해 주어진 값부터 시작해 1까지 분해합을 구해보면서 주어진 값과 구한 분해합이 일치할때 현재 찻수를 저장하는 방식으로 해결. 끝까지 분해합이 구해지지 않으면 0을 리턴하게 처리하였다.

 다른 사람들의 풀이법을 여러개 찾아보았는데도 깔끔한 규칙성이 보이는 풀이가 없어서 아쉬운 문제ㅠ

 

풀이 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int num = Integer.parseInt(br.readLine());
        int result = 0;
        int temp, tempResult;
        for(int i=num; i>0; i--) {
            temp = tempResult = i;
            while(temp!=0) {
                tempResult += temp%10;
                temp /= 10;
            }
            if(tempResult==num) {
                result = i;
            }
        }
        
        bw.write(result+"\n");
        
        bw.flush();
    }
}