[백준] 1107 리모컨 - Brute Force (Java)

케이스 분류:

1) 리모컨이 고장나지 않은 경우

2) 리모컨 버튼 몇개 고장난 경우

   2-1) 고장났지만 바로 눌러서 갈 수 있는 경우

   2-2) 바로 눌러서 갈 수 없는 경우

      2-2-1) 100에서 +-로 가는 경우

      2-2-2) 가까운 번호를 누르고 +-로 가는 경우 - 가까운 번호를 찾기 위해 brute force 사용

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

public class Q1107 {

	static int count = 0, target = 0;
	static boolean nums[] = new boolean[10];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int target = Integer.parseInt(br.readLine());
		int broken = Integer.parseInt(br.readLine());

		int result = target - 100;
		if (result < 0) {
			result = -result;
		}

		if (broken == 0) {
			result = possible(target) < result ? possible(target) : result;
			bw.write(result + "");
			bw.flush();
			br.close();
			bw.close();
		} else {
			String str = br.readLine();
			StringTokenizer st = new StringTokenizer(str);

			for (int i = 0; i < broken; i++) {
				nums[Integer.parseInt(st.nextToken())] = true;
			}

			if (possible(target) > 0) {
				result = possible(target) < result ? possible(target) : result;
			} else {

				for (int i = 0; i < 1000000; i++) {
					int c;
					if (possible(i) >= 0) {
						c = target - i;
						if (c < 0) {
							c = -c;
						}
						if (result > c + possible(i)) {
							result = c + possible(i);
						}
					}

				}
			}
			bw.write(result + "");

			bw.flush();
			br.close();
			bw.close();
		}
	}

	static int possible(int num) {

		int clicks = 0;

		if (num == 100)
			return 0;

		if (num == 0) {
			if (nums[0])
				return -1;
			else
				return 1;
		}

		for (int i = num; i > 0; i /= 10) {
			if (nums[i % 10])
				return -1;
			clicks++;
		}

		return clicks;
	}
}