[백준 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을 출력한다.

---

---

코드1

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

public class BJ2231 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int k = 0;		// 몇 자리 수인지 저장해 둘 변수
		int temp = n;	// 임시로 사용할 변수 temp
		
		// 입력 받은 n이 몇 자리 수인지 구하기
		while(temp != 0) {
			temp /= 10;
			k++;
		}
		
		// TEST
//		System.out.println("n은 " + k + "자리수");
		
		// n-3*k 부터 분해합 구하기
		temp = n - 9 * k;
		while(sum(temp) != n) {
			// TEST
//			System.out.println("temp는 " + temp);
			temp++;
		}
		
		System.out.println(temp);
		
	}
	
	static int sum(int m) {
		int result = m;
		
		while(m != 0) {
			result += m % 10;
			m /= 10;
		}
		
		return result;
	}
}

엥? 시간 초과요? 

으음 그럼 sum 함수에 m(생성자)과 n(입력값)을 넘겨주고 분해합이 n을 넘으면 바로 0을 return 하도록 하자.

---

코드2

sum 함수에 이렇게 코드를 추가해봤지만 역시나 또 시간 초과...

전 어떻게 해결해야할지 모르겠는데요?

---

코드3

코드 잘 돌아가고 있는지 콘솔에 값들을 찍어보면서 가장 큰 입력값으로 테스트를 돌려보는 와중에 문제를 발견했다.

입력값은 100000이었는데 1000000이 훨씬 넘는 값까지 계속 돌아가고 있었다! 생성자는 입력값보다 클 수 없으므로 temp 값이 입력값을 넘어서면 해당 숫자는 생성자가 없는 숫자가 된다. 

그럴 경우 0을 출력하라고 친절히 나와있는데 문제를 꼼꼼히 안본 내 탓... 그리고 수정한 코드!

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

public class BJ2231 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int k = 0;		// 몇 자리 수인지 저장해 둘 변수
		int temp = n;	// 임시로 사용할 변수 temp
		
		// 입력 받은 n이 몇 자리 수인지 구하기
		while(temp != 0) {
			temp /= 10;
			k++;
		}
		
		// n-3*k 부터 분해합 구하기
		temp = n - 9 * k;
		while(sum(temp, n) != n && temp < n) {
			temp++;
		}
		
		if(temp == n) {
			System.out.println("0");
		} else {
			System.out.println(temp);
		}
	}
	
	static int sum(int m, int n) {
		int result = m;
		
		while(m != 0) {
			result += m % 10;
			m /= 10;
			
			if(result > n) {
				return 0;
			}
		}
		
		return result;
	}
}