[JAVA] 백준 2231번 분해합 : 브루트 포스

2231번: 분해합

 

1. 문제 추상화

 

임의의 값 M이 주어질 때, M의 생성자(N) 중 최소값을 구하라.

( 생성자(N)는 생성자와 생성자 각 자리 수의 합이 M과 같은 수를 의미한다. )

 

 

2. 알고리즘

 

생성자(N)의 각 자리수의 합을 SUM이라 하겠다.

 M = N + SUM 이므로 M > N이다.

 

그러므로

 

가장 쉬운 방법은 1부터 M까지 모든 경우의 수를 조사하는 방법이다. (브루트 포스) 그러나 M은 1 ≤ M ≤ 1,000,000 이므로 경우의 수를 줄이는 것이 좋다.

 

M = N + SUM이므로 N = M - SUM이다. 

고로, SUM의 범위에 따라 N의 범위가 정해진다.

 

▷ SUM의 범위

N이 한 자리 수인 경우 : 1 ~ 9 ( 9 X 1 )

N이 두 자리 수인 경우 : 1 ~ 18 ( 9 X 2 )

N이 세 자리 수인 경우 : 1 ~ 27 ( 9 X 3 )

N이 네 자리 수인 경우 : 1 ~ 36 ( 9 X 4 )

 

그럼 N은 몇 자리 수일까?

 

1 ≤ M ≤ 1,000,000 이므로 M은 1,000,000을 제외하면 최고 6자리이다. M > N이므로 N도 6자리 이하이니 SUM은 1 ~ 54 가 최대이다. 그러므로 두 단계 낮은 자리 수의 N이 M의 생성자가 될 수 없다. 

 

고로, M의 자리 수가 세 자리면 N도 세 자리거나 한 단계 낮은 두 자리 수이다. 

 

M이 자리수가 k 라면

1) N이 k 자리수인 경우 : M - SUM(k)의 최대값 ≤ N < M

2) N이 k-1 자리수인 경우 : M - SUM(k-1)의 최대값 ≤ N < M

 

두 가지 범위를 브루트 포스(Brute Force) 방식으로 탐색하여 적절한 값을 구한다.

 

3. 코드

 

import java.util.Scanner;

public class Main {

	public static final int MAX_VALUE = 1000000;
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int value = sc.nextInt();
		
		int numberOfValue = String.valueOf(value).length(); // M의 자리수(k) 파악
		int bigScope = 9*numberOfValue; //  k인 경우, SUM의 최대값
		int smallScope = 9*(numberOfValue-1); // K-1인 경우, SUM의 최대값
		
		int minOfBigScope = getGenerator(value,bigScope); // k인 경우, 생성자 중 최소값 탐색
		int minOfSmallScope = getGenerator(value,smallScope); // k-1인 경우, 생성자 중 최소값 탐색
		
		System.out.println(getResult(minOfBigScope,minOfSmallScope)); // 결과 도출
	}
	
	public static int getGenerator(int value, int scope) {
		int min = MAX_VALUE;
		for(int i=(value - scope); i < value; i++) {
			boolean result = isGenerator(value,i);
			if(result) {
				if(i < min) {
					min = i;
				}
			}
		}
		return min;
	}

	public static boolean isGenerator(int value, int data) {
		int sum = 0;
		int tmp = data;
		while(tmp != 0) {
			sum += tmp % 10;
			tmp /= 10;
		}
		
		if(value == data+sum) {
			return true;
		}else {
			return false;
		}
	}
	
	
	public static int getResult(int data1, int data2) {
		int result = Math.min(data1, data2);
		if(result != MAX_VALUE) {
			return result;
		}else {
			return 0;
		}	
	}

}