[백준-Java] 브루트 포스 2번

오늘은 한 문제만 간단하게(?) 풀이하겠다.

2231번) 분해합

이 문제를 꽤 오랜시간 고민한 이유가 있다.

주어진 N과 그에 맞는 생성자를 찾는 과정에서 자릿수마다 하나씩 숫자를 고르려고 생각을 했기 때문이다.
예를 들어, 123이 생성자이면 1, 2, 3 따로따로 찾으려고 생각했기 때문에 오래걸렸다.

조금만 다르게 보면 쉽게 풀릴 문제였다.

우리는 생성자를 '탐색'해야한다. 이를 위해 범위부터 정해보자.

가장 간단하게 생각할 수 있는 범위는 '생성자 < N' 이다.
다음은 시작범위인데, 시작범위는 N-자릿수*9 이다.
N은 생성자와 생성자의 각자릿수의 합인데, 각 자릿수의 최댓값은 9이고 이는 N의 자릿수만큼 더해질 수 있기 때문이다.

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

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 len = (int)(Math.log10(N)+1);
        int result = 0;

        for(int i = (N-len*9); i < N; i++){ // 최솟값 지정
            int num = i;
            int var_num = i; // 변해야하는 값 지정
            int sum = 0;
            while(var_num != 0){
                sum += var_num%10; // 각 자릿수의 합
                var_num /= 10;
            }
            if(num+sum == N){
                result = num; // 조건에 들지 않으면 result는 0
                break; // 최솟값을 찾으므로 반복문 종료
            }
        }
        System.out.println(result);
    }
}

코드를 어떻게 써서 풀어내느냐도 중요하지만 문제를 해결하는 방법을 생각해내는 것이 훨씬 중요하다고 느낀 문제였다.