백준 BAEKJOON[2231] : 분해합 - JAVA (Class-2)

문제 링크 : www.acmicpc.net/problem/2231

3052번: 나머지

문제

어떤 자연수 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

---

클래스2부터 난이도가 급상승한듯 하다.

운영하고 있는 프로젝트가 어제 메인개편을 끝내 그동안 문제를 풀지 못하였다.

 

이번 문제는 브루트 포스를 이용하여 풀어보려 생각은 했지만 다른 방법이 있을것이라 생각하여 오래도록 고민했지만 도저히 풀리지가 않아 검색을 해보았다. 

검색을 한 후 허탈하였다. 이번 문제는 브루트 포스로 푸는 문제였던 것이다.

브루트 포스도 훌륭한 알고리즘의 하나인데 나는 그것을 무시해버렸던게 바보같았다.

 

해답

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		
		int n = sc.nextInt(); 
		int nLength = Integer.toString(n).length(); //길이를 구해준다
		int maxMinus = nLength * 9; 
		int minNumber = n-maxMinus; // 길이 * 9를 함으로써 3자리면 n-27 4자리면 n-36 .... 이 되도록
		int result= 0;
		
		for(int i=minNumber; i<n; i++) {
			int sum = 0;
			int temp=i;
			for(int j=0;j<nLength;j++) {
				sum+= temp%10;	
				temp/=10;
				
			}
			
			if(sum + i == n) {
				result=i;
				break;
			}
		}
        
		System.out.println(result);
	}
}

 

이번 문제는 혼자서 해결하지  못하였기 때문에 마음에 들지 않는다.

브루트 포스를 이용하긴 하였지만 n의 자리수*9만큼을 n에서 빼줌으로써 범위의 최소값을 정해주고 n까지 반복문을 돌린다면 2부터 n만큼 돌리는것보다 현저히 반복의 횟수가 줄어드는것이 포인트다.

 

오늘은 모니터를 새로 구매하여 기분이 좋았지만 화상 면접을 통하여 내가 얼마나 부족한지에 대해서 다시한번 느끼게 된 날이었다.

코딩테스트를 위한 알고리즘 공부도 좋지만 기본적인 알고리즘, 자료구조에 대해서 많이 공부해야 한다는 다짐을 하게되었다.

묵묵히 학습을 한다면 더 좋은날이 올것이라 생각한다.

힘내자.