[백준 2231] 분해합

문제

 

 

자연수의 범위가 최대 1000000 이고 시간복잡도가 O(n2) 이상일 수 없으므로 완전탐색으로 접근했다.

 

 

 

1. 가장 작은 생성자를 구해야하니 연산할 숫자는 작은수에서 증가한다.

2. 생성자는 입력한 자연수보다 작으니 반복 범위는 n 보다 작을때이다.

 

 

 

 

Java

 

public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        int i=0, sum=0;
        while(i<=n){
            i++;
            int se = i;
            sum = se;
            while(se >= 1){
                int div = se%10;
                se /= 10;
                sum += div;
            }
            if(sum == n){
                System.out.println(i);
                break;
            }
            if(i == n)
                System.out.println(0);
        }
}