2231번 - 분해합

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

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());
        for(int i=1;i<N;i++) {
            int pos_sum = 0;
            int self = i;
            int logarithm = (int)Math.log10(i);
            while(logarithm >= 0) {
                pos_sum += (self / (int)Math.pow(10, logarithm));
                self = self % (int)Math.pow(10, logarithm);
                logarithm--;
            }
            if(pos_sum + i == N) {
                System.out.println(i);
                System.exit(0);
            }
        }
        System.out.println(0);
        br.close();
    }
}

 

이 문제는 위 방법 대신 문자열의 각 자리를 숫자로 바꾸는 것을 추천드립니다.

위 방법은 948ms가 나오는 등 시간 차이가 매우 큽니다.

 

해결 아이디어는 다음과 같습니다.

 

1. N이 50만까지이므로 브루트 포스 방법 이용(1부터 자기 자신-1까지 모든 수를 테스트합니다.)

2. 상용로그의 진수를 이용해 각 자릿수의 숫자를 추출해 더합니다.(pos_sum)

3. 자기 자신(i)과 자릿수 합(pos_sum)을 더한 값이 N과 같으면 해당 i(최솟값)을 출력하고 프로그램을 종료합니다.

4. 해당하는 i가 없을 경우(for문이 출력 없이 끝난 경우) 0을 출력합니다.

 

2번이 조금 성가신 데 126이라 하면 10의 2승으로 나눈 1을 더하고 나머지인 26을 다시 갖다가 10의 1승으로 나누는 식입니다. 이 부분을 그냥 문자열 추출로 처리하면 매우 빨라질 것으로 보입니다.