CodingTest # 22 Java 2231 (분해합) 문제 풀이

출처  핀터레스트

2231

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

public class Test2231 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String N = br.readLine();

        int valueLength = N.length();
        int value = Integer.parseInt(N);

        int result = getInitialNum(value, valueLength);
        System.out.print(result);
    }

    private static int getInitialNum(int value, int valueLength) {
        for(int i = (value - (valueLength * 9)); i < value; i++) {
            int sum = i + getCharNumSum(i);
            if(sum == value) {
                return i;
            }
        }
        return 0;
    }

    // 각 자릿수의 합
    private static int getCharNumSum(int value) {
        int returnValue = 0;
        while (value != 0) {
            returnValue += value % 10;
            value /= 10;
        }
        return returnValue;
    }
}

 

https://st-lab.tistory.com/98

[백준] 2231번 : 분해합 - JAVA [자바]

 

이번에도 stranger님의 블로그에서 많은 도움을 얻었다.

 

우선 입력받은 N에 대한 가장 작은 생성자를 구해야 하는 문제이다.

 

생성자를 K라고 했을 때,

 

식은 다음과 같다.

 

N = K + (K의 각 자릿수의 합)

 

하지만 우리가 구하려는 것은

 

K(생성자) 이다.

 

저 식을 이항 하게 되면,

 

K = N -  (K의 각 자릿수의 합)

 

라는 식이 나오게 된다.

 

 

처음 이 문제를 풀었을 때는 막무가내로 생성자를 찾기 위해

 

1부터 ~~ 생성자가 나올 때까지

 

for문과 while문을 돌렸는데,

 

역시나 생성자의 값이 높을 때는 시간 초과가 나왔다.

 

해결법은 생성자가 나올 수 있는 최소 범위부터 올라가는 것이었다.

 

K = N -  (K의 각 자릿수의 합) 식처럼

 

최소 범위가 나오게 하려면  (K의 각 자릿수의 합)의 값이 최댓값인 상태에서

 

N 값의 빼야 했다.

 

그러려면 각 자릿수가 모두 최대로 나올 수 있는 수인 9가 나와야 했다.

 

고로 몇의 자리 * 9라는 식으로 K 값을 구해 최소로 나올 수 있는 생성자의

 

범위를 구하고 차례로 올라가는 것이다.