백준 2231

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

public class Main2231 {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		
		int N = Integer.parseInt(br.readLine());
		
		for(int i=1; i<=1_000_000; i++) {
			int sum = i;
			
			String s = i+"";
			for(int j=0; j<s.length(); j++) {
				sum += s.charAt(j) - '0';
			}
			
			if(sum == N) {
				System.out.println(i);
				System.exit(0);
			}
		}
		System.out.println(0);
		
		
	}

}

시간복잡도 : O(N), 입력제한 1,000,000, 시간제한 2초 

-> 완전탐색 이용 

자연수 N을 이용하여 자연수 M을 만들수 있다. (분해합)

N은 M의 생성자

M의 분해합은 M보다 크다.

M의 생성자 N은 반드시 M보다 작다.

N<=M 

분해합을 해보면서 N이 등장할때를 구하면 된다.