Baekjoon2231: 분해합

문제

어떤 자연수 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을 출력한다.

 

추상화

0. 생성자의 범위를 탐색한다
1. N은 1,000,000까지 값을 가진다
2. 어떤 분해합이 문자열로 ABC(3자리수)라면?
          → 생성자는 ABC를 넘을 수 없다
          → 분해합의 최대값은 999이므로 생성자의 크기는 998이 최대이다
          → 생성자 + 각 자리수 = 분해합 이므로 각 자리수의 합의 최대값은 9+9+8이다
3. 2번에 의해 생성자의 범위는 다음과 같다(n = 분해합의 자리수)
          → 분해합-(9*n-1)<= 생성자 <= 분해합
4. 입력값 N에 대해 자리수를 파악하고 자리수 n에 대해 9*n-1을 빼준 뒤 분해합연산을 시작한다
5. 분해합 값과 같아지면 가장 작은 생성자이다.

import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	 String s = br.readLine();
	 int n = s.length(); //N의 자리수를 가져온다
	 int N = Integer.parseInt(s);
	 int start = N-9*n; //시작은 N-N의 자리수x9
	 int sum = 0; //while조건에 넣어야 하므로 내부에서 sum을 만들 수 없다
	 int i = 0;  // 분해합을 얻어낼 임시 저장소
	 int fix = 0; //값을 출력하기 위해 이번 loop의 숫자를 저장
	 int plus = 0;  //while loop마다 증가
	 boolean out = true; //while을 빠져나오도록 해준다
	 while(sum != N && out) {
		 sum =start + plus;
		 i = start + plus;
		 fix = start + plus;
		 while(i!=0) {
			 sum += i%10;
			 i /= 10;
		 }
		 if(sum == N) {
			 System.out.print(fix);
		 }
		 if(fix==N) {
			 System.out.print(0);
			 out = false;
		 }
			 plus++;
	 }
}
}