[백준] 1107. 리모컨

문제 링크

[백준] 1107. 리모컨

풀이 과정

주어진 N이 100이면 현재 틀어져 있는 채널이 100번이므로 이동하지 않아도 됩니다.

N이 100이 아닌 다른 수라면, 망가지지 않은 리모컨 버튼을 조합해 채널 번호를 만들고, 만들어진 채널 번호(채널 번호의 길이가 버튼을 누른 횟수)로부터 목적지 채널인 N까지의 차(+, - 버튼을 누른 횟수)를 구하여 정답을 구합니다.

문제를 풀면서 마주친 애를 먹었던 부분은 아래 코드와 같습니다.

if (N == 100)
    System.out.println(0);
else if (allBroken) {
    System.out.println(Math.abs(N - 100));
} else {
    solve(0, new StringBuilder());
    System.out.println(ans);
}

리모컨의 +, - 를 제외한 모든 숫자 버튼이 망가져 있을 경우에만 N-100을 답으로 출력했다는 점인데, 이는 아래 예시와 같은 반례가 존재했습니다.

위와 같이 숫자 5 버튼을 제외한 나머지 버튼들이 모두 망가져 있을 경우, allBroken이 false가 되어 solve 메소드를 실행하게 되고 최소값은 258이 됩니다.

하지만, 초기 100번 채널에서 +를 100번 눌러 이동하는 것이 더 적은 횟수의 버튼을 누르는 경우가 되므로 잘못된 분기였음을 알게 되었습니다.

allBroken 이라는 모든 버튼이 망가졌다는 상황을 boolean 변수로 갖고 있을 필요가 없을 뿐더러, 위와 같은 예외 상황을 대비해 초기 ans 값을 Math.abs(N-100)으로 설정해둔 다음 재귀를 돌리면 올바른 정답을 도출하게 됩니다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N, M;
    static boolean[] remocon;
    static int ans;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        ans = Math.abs(N - 100);

        remocon = new boolean[10];
        Arrays.fill(remocon, true);

        for (int i = 0; i < M; i++)
            remocon[sc.nextInt()] = false;

        if (N == 100)
            System.out.println(0);
        else {
            solve(0, new StringBuilder());
            System.out.println(ans);
        }
    }

    private static void solve(int depth, StringBuilder sb) {
        if (!sb.toString().equals("")) {
            int diff = Math.abs(N - Integer.parseInt(sb.toString()));
            int len = sb.length() + diff;

            ans = Math.min(ans, len);
        }

        if (depth == Integer.toString(N).length() + 1) {
            return;
        }

        for (int i = 0; i < remocon.length; i++) {
            if (remocon[i]) {
                sb.append(i);
                solve(depth + 1, sb);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }
}