[백준] [2231] 분해합 (브루트포스) (JAVA)

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

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 복사

216

예제 출력 1 복사

198

---

※ JAVA 코드 (분해합)

import java.io.*;

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());
		
		String str = "";
		// 각자리수의 합을 더할 숫자
		int tmpNum = 0;
		// 0부터 순차적으로 시작
		int M = 0;
		// 증가값 M이 N이 될때까지 증가
		while(M <= N) {
			tmpNum = 0;
			M++;
			str = String.valueOf(M);
			// 각 자리수를 합한다
			for(int i = 0; i < str.length(); i++) {
				tmpNum += (int) str.charAt(i)-'0';
			}
			// 생성자를 찾았다면 M출력 후 종료
			if(N == M + tmpNum) {
				System.out.println(M);
				return;
			}
		}
		// 생성자를 찾지 못한다면 0출력
		System.out.println(0);
	}
}

---

※ 생각정리 (분해합)

처음 들었던 생각은 브루트포스에 맞게 입력받은 N까지의 모든 수를 돌며 M을 0부터 증가하고 M과 M의 각 자리수를 전부 더하여 값을 찾아 보는 방법이었다.

0부터 시작하기에 O(N) 정도의 시간복잡도가 나올 수 있으며, 결과는 

---

상당히 처참한 결과라고 할 수 있다.

그래서, 시간복잡도를 줄일 수 있을지 모르겠다는 생각을 해보았다.

반복문의 시작을 0이아닌 생성자가 나올 수 있는 최대수를 찾아보았다. N - 9 x (숫자의 길이) 각 자리수가 모두 9일경우 만들 수 있는 최대 수가 나오기때문에 시작 숫자를 N - 9 x (숫자의 길이)로 정하였다.

이때 만약 1000000의 숫자가 입력값으로 들어온다면 1000000 - 9 * 7 = 999937부터 1000000까지의 수를 반복하면 된다.

기존의 0부터 1000000까지보다 훨씬 빠르게 반복문을 마칠 수 있었다.

---

※ JAVA 코드 (분해합) 수정본

import java.io.*;

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());
		
		String str = "";
		// 각자리수의 합을 더할 숫자
		int tmpNum = 0;
		// 0부터 순차적으로 
		String s = Integer.toString(N);
		int M = N - 9 * s.length();
		// 증가값 M이 N이 될때까지 증가
		while(M <= N) {
			tmpNum = 0;
			M++;
			str = String.valueOf(M);
			// 각 자리수를 합한다
			for(int i = 0; i < str.length(); i++) {
				tmpNum += (int) str.charAt(i)-'0';
			}
			// 생성자를 찾았다면 M출력 후 종료
			if(N == M + tmpNum) {
				System.out.println(M);
				return;
			}
		}
		// 생성자를 찾지 못한다면 0출력
		System.out.println(0);
	}
}

결과는

 

시간을 줄이기위해 확인할 필요가 없는 수들을 체크하는게 얼마나 중요한지 깨달을 수 있었다.

 

-새벽코딩-