백준 12348번 : 분해합2 (G5)

문제

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

---

풀이 방법

분해합은 생성자와 각 자릿수를 모두 더한 숫자인데, 각 자릿수를 모두 더한 수는 그렇게 큰 수가 아니다.

ex) N = 12345 인 경우
N은 5자리 숫자이기 때문에
각 자릿수는 가장 커봐야 9+9+9+9+9 일 것이다.
즉, 9 * 5자리 = 45
그렇다면 생성자는 12345 - 45 = 12300 보다 항상 크거나 같을 수 밖에 없다.
결국 12300 부터 12345 중에서만 생성자를 찾으면 된다.

즉, 입력받은 정수 N 에 대하여 자릿수의 길이만큼 9를 빼주면 된다.

그 미만의 수는 생성자가 될 수 없다는 것이다.

1. 주어지는 숫자의 자릿수 구하기
2. 검사를 시작할 수치 구하기 -> 자릿수에 따라 다름
3. N - (9 × N의 길이) 부터 탐색하여 N 까지만 반복문을 돌면서, 분해합이 N과 동일한지 비교

---

코드

package day0207;

import java.io.*;
import java.util.*;

public class BOJ_G5_12348_분해합2 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String input = br.readLine();
		long N = Long.parseLong(input);
		
		int digit = input.length();		// 문자열의 길이 (=입력값의 자릿수)
		long start = N - digit*9;		// 가능한 최솟값인 'N - 9*(N의 자릿수)' 부터 시작
		
		for(long i=start; i<N; i++) {
			long num = i;
			long sum = num;
			
			while(num>0) {
				sum += num % 10;	// 각 자릿수 더하기
				num /= 10;
			}
			
			if(sum == N) {	// 생성자를 찾았을 경우
				System.out.println(i);
				return;
			}
		}
		
		System.out.println(0);	// 생성자가 없는 경우
	}
}