백준/1104 리모콘

작성일 | In

< 문제 분석 및 풀이 방법 >

Backjoon :: 리모콘 문제는 브루트 포스를 활용하는 문제다.

  • 모든 경우의 수를 다 해보고 최소값을 찾으면 된다.
  • 2가지로 나눠서 생각하면 쉽게 접근할 수 있다.
  1. 초기값 100에서 +, - 만을 활용해 이동할 때 필요한 cnt
  2. 새로운 값을 입력받아서 해당 값에서부터 +, -로 이동할 때 필요한 cnt
  • 특히 2번의 경우에는 새로운 값이 1자리 숫자 ~ 6자리 숫자까지 가능하는 점을 인지해야 한다.

< 소스 코드 >

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.io.*;
import java.util.*;

public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static boolean[] button = new boolean[12];
    public static int ans = Integer.MAX_VALUE;
    public static int n;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        if (m != 0) stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            String s = stk.nextToken();
            if (s.equals("+")) s = "10";
            if (s.equals("-")) s = "11";
            button[Integer.parseInt(s)] = true;
        }
        //초기값 100에서 갈 수 있는 최단경로값 계산
        if (!button[10] && (100 - n) >= 0) ans = Math.min(ans, 100 - n);
        if (!button[11] && (n - 100) >= 0) ans = Math.min(ans, n - 100);
        //0~9까지 모든 경우의 수 탐색
        for (int i = 0; i < 10; i++) {
            if (!button[i]) dfs(i, 1, 1);
        }
        System.out.println(ans);
    }

    public static int dfs(int num, int len, int cnt) {
        if (len > ans) return Integer.MAX_VALUE;    //현재 답보다 커지면 가지치기
        if (cnt == 6) {     //6개의 숫자를 골랏을 때
            return ans = Math.min(ans, getRes(num, len));
        }
        for (int i = 0; i < 10; i++) {
            if (i == 0) {   //6자리가 아닌 수
                dfs(num, len, cnt + 1);
            }
            if (!button[i]) {   //6자리를 만드는 경우
                dfs(num * 10 + i, len + 1, cnt + 1);
            }
        }
        return Integer.MAX_VALUE;
    }

    public static int getRes(int num, int cnt) {
        if (n == num) return cnt;
        if (!button[10] && n > num) return cnt + n - num;
        if (!button[11] && n < num) return cnt + num - n;
        return Integer.MAX_VALUE;
    }
}