[백준 2231 / JAVA] 분해합

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

2231번: 분해합

 

브루트포스 문제이다.

 

입력 받은 수보다 작은 수 중 생성자인 가장 작은 수를 찾으면 된다.

단순히 반복문으로 작은 수부터 찾았다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        int N, num, sum;
        String input;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        input = br.readLine();
        N = Integer.parseInt(input);

        for (int i = N - 9 * input.length(); i < N; i++) {
            num = i; //임시 수
            sum = i; //분해합
            while (num > 0 && sum <= N) {
                sum += (num % 10);
                num = num / 10;
            }
            if (sum == N) {
                System.out.println(i);
                return;
            }
        }
        System.out.println(0);
    }
}

 

처음에는 반복문을 1부터 돌렸는데 다른 풀이를 찾아보니 수에서 자리 수 * 9 만큰 빼준 수부터 시작했다.

각 자리수가 1부터 9까지(0은 합해도 상관없으니) 올 수 있으니 그만큼 뺀 수부터 시작했다.