[백준 | Java] 1107 리모컨

내 풀이

이 문제는 숫자를 전부 눌러서 N과 일치할 때 최소인 값을 찾는 문제이다.

구현을 위해 다음의 세 가지 경우를 고려해야한다.

1. N이 100일 때는 바로 0 출력

2. +, - 버튼만을 사용

3. 숫자 버튼을 사용해 근사치까지 누른 다음 +, - 사용

2번은 N-100으로 구할 수 있으며,
3번은 DFS를 이용해 고장나지 않은 숫자버튼으로 누른 수에서 N까지 +, -를 최소로 사용한 값을 구하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static boolean[] broken;
    static int N;
    static long cnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        broken = new boolean[10];
        if (M > 0) {
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++) {
                int num = Integer.parseInt(st.nextToken());
                broken[num] = true;
            }
        }

        // N == 100일 경우 0 반환
        if (N == 100) {
            System.out.println(0);
            return;
        }

        cnt = Math.abs(N - 100);
        dfs(0, 0);
        System.out.println(cnt);
    }

    public static void dfs(int idx, int click) {
        for (int i = 0; i < 10; i++) {
            // 고장나지 않은 숫자 버튼으로 누른 수 카운팅
            if (!broken[i]) {
                int newBtn = click * 10 + i;
                int cnt2 = Math.abs(N - newBtn) + String.valueOf(newBtn).length();
                // N - 100의 절댓값 구해서 숫자로 최대한 눌렀을 때와 +,- 버튼으로만 눌렀을 때 비교
                cnt = Math.min(cnt, cnt2);

                // 채널의 최대가 6자리
                if (idx < 6) {
                    dfs(idx + 1, newBtn);
                }
            }
        }
    }
}