[자바]백준 2231번 분해합[브루트포스][엄탱]

문제 링크

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

2231번: 분해합

해설

해당 문제는 브루트포스 알고리즘으로 분류 되어 있다.

또한, 주어진 자연수의 범위가 최대 1,000,000 이고 자리수는 최대 7번 이기 때문에 최악의 경우의 수는 7,000,000 이다.

물론, 주어진 수가 1,000,000이면 당연히 1,000,000이 답이 될 수 없어서 최악의 경우의 수가 7,000,000보다 작다

하지만 브루트포스 알고리즘은 무식하게 완전 탐색하는 알고리즘이고 그에 맞게 무식하게 완전 탐색 해서 풀어봤다.

 

풀이는 간단하다 1부터 주어진 수 N까지 반복하여 나온 수(A)와 나온 수(A)의 자리수 각각을 다 더해서 N이 나오면 출력해주면 된다.

코드 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        N = Integer.parseInt(br.readLine());
        
        System.out.println(getConstructor());
        br.close();
    }
    
    public static int getConstructor() {
        for (int i = 1; i < N; i++) {
            int result = 0;
            
            int temp = i;
            
            // 자리수 더해주기
            while (temp != 0) {
                result += temp % 10;
                temp /= 10;
            } 
            
            if (result + i == N) {
                return i;
            }
        }
        
        return 0;
    }
}