[백준 / JAVA] 1107. 리모컨 (G5)

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

1107번: 리모컨

 

(절대 이 문제를 구현하려 하지마...)

이 문제를 본 프로그래머들은 다들 구현으로 풀다가 좌절한다. (아니면 골드가 아님) 이 문제를 구현하려면 고려해야 하는 상황이 참 많은데 내가 파악한 것만 나열하면 (N은 목표로 하는 수)

 

1. N이 K자리 수일때 K+1 자리 수 중 만들 수 있는 가장 작은 수

2. N이 K자리 수일때 K-1 자리 수 중 만들 수 있는 가장 큰 수

3. N의 첫 번째 자리 수 N1이 사용 불가능할 때 N1과의 차가 가장 작은 수 N(min)가 N1<N(min) 라면 N2로 시작하는 K자리 수 중 만들 수 있는가장 큰 수 (예: N1=5, N(min)=3)

4. N1이 사용 불가능할 때 N1과의 차가 가장 작은 수 N(min)가 N(min)>N1 라면 N2로 시작하는 K자리 수 중 만들 수 있는 가장 큰 수 (예: N1=5, N(min)=7)

5. N1이 사용 불가능할 때 N1과의 차가 가장 작은 수가 두개라면, 즉 N(min1)<N1<N(min2) 라면 N(min1)으로 시작하는 K자리 수 중 가장 큰 수와 N(min2)로 시작하는 수 중 가장 작은 수를 비교

6. N1이 사용 가능하면 재귀로 들어가서 N2를 기준으로 6, 5, 4, 3 번을 반복해야함. (즉, 재귀로 구현해야 한다...)

7. N이 100에 가까울 경우 (이 경우는 그나마 쉽다)

 

이정도이니 능력이 안되면 곱게 완전탐색을 하자. 완전탐색을 할때 팁을 주자면

 

1. N의 범위가 0<=N<=500000 인데 N이 25만보다 작다면(경우 A라고 하자) 0부터 찾고 25만보다 크다면(경우 B) 50000부터 역으로 찾자.

2. 1에서 경우 A라면 만들 수 있는 수와 N의 차가 양수가 될 때 멈추고, 경우 B라면 만들수 있는 수와 N의 차가 음수가 될 때 멈춘다. (A의 경우 차가 양수가 되는 순간, B의 경우 차가 음수가 되는 순간 절대값이 증가하기만 해서 더 볼 필요 X)

 

구현을 포기하면 편해질 수 있다

 

import java.io.*;
import java.util.*;

class Main {
	static boolean canMake(int input) {
		int tmp;
		if(input == 0 )
			if(button[0]==1)
				return false;
		while (input != 0) {
			tmp = input % 10;
			if (button[tmp] == 1)
				return false;
			input /= 10;
		}
		return true;
	}

	static int step(int channel, int n) {
		int gap = Math.abs(n - channel);
		int length = Integer.toString(channel).length();
			return gap + length;
	}

	static int button[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());
		button = new int[10];
		int channel = 100;
		int step = step(n, channel);
		int m = Integer.parseInt(br.readLine());
		if (m != 0) {
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < m; i++) {
				button[Integer.parseInt(st.nextToken())] = 1;
			}
		}
		boolean bigNum = false;
		if (n > 500000 / 2)
			bigNum = true;

		if (bigNum) {
			for (int i = 999999; i >= 0; i--) {
				if (canMake(i)) {
					step = Math.min(step, step(i, n));
					if (i < n)
						break;
				}
			}
		} else {
			for (int i = 0; i <= 999999; i++) {
				if (canMake(i)) {
					step = Math.min(step, step(i, n));
					if (i > n)
						break;
				}
			}
		}
		System.out.println(Math.min(step, Math.abs(n-100)));
	}
}