[JAVA] 백준 알고리즘 2231번 문제 풀이 (분해합)

 

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

2231번: 분해합

 

소스코드

import java.io.*;

public class Sanizzang {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String digit_n = br.readLine();
        int digit_len = digit_n.length();

        int N = Integer.parseInt(digit_n);
        int M = 0;

        for (int i = (N - (digit_len * 9)); i < N; i++) {
            int num = i;
            int sum = 0;

            while (num != 0) {
                sum += num % 10;
                num /= 10;
            }

            if (sum + i == N) {
                M = i;
                break;
            }
        }

        System.out.println(M);
    }
}

 

코드설명

1. N값을 문자열로 받아와 N값의 자리수를 digit_len 변수에 저장한다.

2. 이 문제는 N값 이하의 모든 숫자들을 비교해볼 필요 없이 N의 자리수 만큼의 9를 곱해서 N에 뺀 만큼의 반복만 하면된다.

3. i의 각 자리수를 더한 값과 i를 더해서 나온 값이 N과 같다면 그때 i를 M값에 대입하고 반복문을 끝내면 가장 작은 생성자를 구해낼 수 있다.