백준 2231번: 분해합 - java

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

2231번: 분해합

<코드>

package Decomposition;

import java.util.Scanner;

public class Decomposition { // 분해합 N이 주어졌을 때 N의 가장 작은 (생성자)를 구하는 프로그램
    public static void main(String[] args) {
        int decompos; // 분해합 N <입력하는 값>
        int constructor = 0;// 생성자 <구하려는 값>
        int digit = 0; // N의 자릿수
        int minConstr; // minConstr: 자릿수*9로, 생성자는 이것보다 항상 크거나 같다
        int digitConstr = 0; //
        int[] digitNum = new int[10];
        int sum = 0;

        Scanner sc = new Scanner(System.in);
        System.out.println("decompos: ");
        decompos = sc.nextInt();
        System.out.println("[test] decompos: "+decompos);

        int n = decompos;

        // 자릿수 구하는 로직
        while (n != 0) {
            n /= 10;
            digit++;
        }

        System.out.println("[test] decompos: "+decompos);
        System.out.println("[test] digit: "+digit);

        minConstr = decompos - 9 * digit;
        System.out.println("[test] minConstr: "+minConstr); // 생성자 중에 최소
        // 자릿수는 가장 커봐야 999... 생성자는 (decompos) - 999... 보다 항상 크거나 같을 수밖에 없다

        // 브루트포스: minConstr부터 decompos까지 (k)+(k 각 자릿수의 합)이 decompos가 되는 수를 구한다
        for(int i = minConstr; i <= decompos; i++) {
            int digitIndex = i;
            int k = i;
            int m = i; // 반복문의 현재 인덱스(k)
            System.out.println("[test] i: "+i);
            while (m != 0) { // 현재 인덱스의 자릿수를 구한다
                m /= 10;
                digitConstr++; // digitConstr: 반복문의 현재 인덱스의 자릿수
            }
            System.out.println("[test] digitConstr: "+digitConstr);

            System.out.println("[test] k: "+k);
            while (k != 0) {
                sum += k % 10;
                k /= 10;
            }
            System.out.println("[test] sum of digit: "+sum);
            if (digitIndex + sum == decompos) {
                constructor = digitIndex;
                break;
            }
            sum = 0;
            digitConstr = 0;
        }

        System.out.println("constructor: "+constructor);
    }


}

<실행>

<풀이>
분해합 216의 가장 작은 생성자는 198이다.
이걸 빨리 구하는 방법은 (모든 경우를 보는 브루트포스 제외)
분해합=생성자+(생성자의 각 자릿수의 합) 이므로
(생성자의 각 자릿수의 합)은 제일 커봤자 9+9+9+... 이런 식으로 됩니다.
분해합 216의 자릿수는 3이므로, (생성자의 각 자릿수의 합)은 제일 큰게 9*3=27
따라서 생성자 = 분해합 - (생성자의 각 자릿수의 합) 이므로
생성자는 216 - 27 = 189 보다는 항상 크거나 같습니다.
189부터 216까지 (생성자)+(생성자의 각 자릿수의 합)이 216이 나오는 (생성자)를 찾으면 됩니다.

<피드백>
변수명 알아볼 수 있게 수정 필요 ?