[문제] 백준 2231번 분해합

* 출처: 백준 단계별로 풀어보기 브루트포스 편

www.acmicpc.net/problem/2231

2231번: 분해합

내 생각

 

1. 첫번째 풀이

 

'순열'스럽게  문제를 풀어봤다. 

다만 범위를 너무 넓게 잡고, 답을 구하더라도 끝까지 탐색하기 때문에 시간이 많이 걸린다. 다른 답안에 비해 10배 이내로 걸리는 듯하다.

 

public class BOJ2231 {
	static int N;
	static int NJari;
	static int numbers[];
	static int answer[];
	static int first = 0;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String s = in.readLine();
		N = Integer.parseInt(s);

		NJari = s.length();
		numbers = new int[NJari]; // 자리수
		answer = new int[NJari]; // 자리수
		permutation(0);
		if(first == 0) {
			System.out.println("0");
		}else {
			System.out.println(arrtoNum());
		}
		
	}
	static String arrtoNum() {
		int tmp = 0;
		for(int i =0;i<NJari;i++) {
			if(answer[i] != 0) {
				tmp = i;
				break;
			}
		}
		String s = "";
		for(int i=tmp;i<NJari;i++) {
			s+= String.valueOf(answer[i]);
		}
		return s;
	}
	static void permutation(int cnt) {

		if (cnt == NJari) {
			int tmp = 0;
			for (int i = 0; i < NJari; i++) {
				tmp += numbers[i];
				tmp += numbers[i] * (int) Math.pow(10, NJari - i - 1);
			}
			if (tmp == N) {
				first++;
				if (first == 1) {
					System.arraycopy(numbers, 0, answer, 0, NJari);
				}
			}
			return;
		}

		for (int i = 0; i < 10; i++) {
			numbers[cnt] = i;
			permutation(cnt + 1);
		}
	}
}

 

2. 두번째 풀이

for문을 통한 완전 탐색. 쉽지만 이것 역시 비효율적이다.

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int result = 0;
		for(int i=1;i<N;i++) {
			int number = i;
			int sum = 0;
			
			while(number!=0) {
				sum += number%10;	// 각 자리수 합
				number /= 10;			
			}
			if(sum+i == N) {
				result = i;
				break;
			}
		}
		System.out.println(result);
	}
}

 

3. 최적화된 풀이

 

N의 생성자를 X라고 할 때,

N = X + (X의 각 자리 합)

=> X = N - (X의 각 자리 합)

즉, X 가 될 수 있는 최소 범위는 X의 각 자리합이 최대가 되면 된다.

N의 자릿수를 NJari라 할 때, X의 각 자리합이 최대가 되려면, NJari 자리수에다가 9로 가득 채워지면 된다.

X >= N - 9 * NJari

 

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		int N = Integer.parseInt(s);
		int NJari = s.length();
		
		int result = 0;

		for (int i = N - NJari * 9; i < N; i++) {
			int num = i;
			int sum = 0;

			while (num != 0) {
				sum += num % 10; // 각 자리수 합
				num /= 10;
			}
			if (sum + i == N) {
				result = i;
				break;
			}
		}
		System.out.println(result);
	}
}