[JAVA] 2231번 분해합

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

예제 입력

216

예제 출력

198

풀이

import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		int answer = 0;
		Scanner sc = new Scanner(System.in);
		
		String n = sc.next();
		int num = Integer.parseInt(n);
		int place = n.length();
		
		String temp = n.substring(0,1);
		for (int i = 0; i < place - 1; i++) {
			temp += "0";
		}
		
		int maxCon = Integer.parseInt(temp) - 1;
		temp = Integer.toString(maxCon);
		
		int sumCon = 0;
		for (int i = 0; i < temp.length(); i++) {
			sumCon += Character.getNumericValue(temp.charAt(i));
		}
		
		for (int i = num - sumCon; i < num; i++) {
			String tmp = Integer.toString(i);
			String[] strArray = tmp.split("");
			int minCon = i;
			for (String s : strArray) {
				minCon += Integer.parseInt(s);
			}
			
			if (minCon == num) {
				answer = i;
				break;
			}
		}
		
		System.out.println(answer);
	}
}

• 최소한으로 루프를 돌려 답을 찾아야 할 것이라는 생각으로 가장 작은 생성자가 될 가능성이 있는 수를 찾기 위한 고민을 많이 하였다.
• M = N + (N의 자리수를 합친 값) 이고, 자리수를 더한 값을 간단하게 F(N)이라고 하겠다.
• F(N)이 최대가 될 N의 값은 9가 가장 많이 속한 자연수일 것이다.
• 예를 들어 216이라면, 199가 F(N)이 가장 크게 나타난다. 14라면 F(N)의 값이 가장 큰 값은 9가 된다.
• 가장 큰 F(N)을 구한다는 것은 입력 값 M이 되기 위해 연산되는 수 중 가장 큰 값을 구한다는 뜻이고,
• M에서 최대 F(N)을 뺀 값이 생성자가 될 가능성이 있는 최소의 수가 될 것이라는 것이다.
• 다시 예제 입력인 216을 예로 들자면, 216의 최대 F(N)값은 199의 자리수를 더한 19(1+9+9)이고, 
• 216-19인 197이 생성자가 될 가능성이 있는 최소값이 된다.
• 따라서 197부터 216까지 루프를 돌며 생성자가 되는 경우가 발생하면 그 값을 출력하도록 하여 코드를 작성하였다.
• 하나더 간단한 예시로 14를 들어보겠다. 14의 최대 F(N) 값은 9이다. 14보다 작은 수 중 어떤 값의 자리수를 더해도 9보다 커지지 않는다. 그러므로 14-9를 한 5가 14의 생성자가 될 가능성이 있는 최소의 수이며, 5부터 14까지 루프를 돌며 값을 찾으면 된다.