리모컨

저는 알고리즘 문제를 풀 때, 우선 완전탐색을 먼저 생각하고 시작하는데요. 컴퓨터의 빠른 연산 능력을 활용하여 문제를 풀 수 있도록 구현하는 능력이 실무에서는 더 중요하지 않을까 하는 생각이 듭니다.

아무튼, 이 문제 역시 완전탐색으로 풀 수 있는데요.

채널의 최댓값은 500,000 입니다. 즉, 6자리의 숫자입니다. 그리고 채널을 +/- 버튼으로 1씩 이동할 수 있으므로, 이는 특정 채널 A에서 특정 채널 B와의 차이만큼 횟수를 누른 것이라고 쉽게 알 수 있습니다.

즉, 기본 아이디어는 이렇습니다.

1. 1자리부터 6자리까지 숫자를 만든다.
2. 숫자를 만들고, 해당 숫자에서 정답 채널까지 갈 수 있는 최솟값을 계산한다.

채널의 최댓값이 500,000 이므로 최대 6자리까지만 만들어보면 됩니다. 만약 채널의 최댓값이 900,000 등과 같았다면 7자리까지 만들어야 됐을 수도 있죠. (참고로 저는 맨 처음에 당연하게 7자리까지 만들어야겠지? 하고 생각해서 풀었는데, 이 포스팅을 작성하면서 다시 생각해보니 6자리까지만 만들어도 된다는 것을 깨닫게 됐습니다. 문제를 수정해서 풀어보니 Java 11 기준으로 180ms -> 136ms가 되었네요!)

자리수를 한 자리씩 늘려가면서 그 때마다 정답을 계산해보면 되는 꽤 간단한 문제입니다.

주의해야 될 점은, 맨 처음 100번 채널에서 시작한다는 점인데요. 이 채널에서 +, -로 정답채널까지의 버튼 횟수를 정답의 후보군으로 넣어봐야 합니다. 예를 들어 정답채널이 99라면, - 한 번으로 정답에 갈 수 있기 때문이죠.

정답

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

public class Main {
    private static final boolean[] broken = new boolean[10];

    private static int target;
    private static int ans = Integer.MAX_VALUE;

    public static void main(String[] args) throws Throwable {
        init();

        solveFirst();

        if (ans == 0) {
            System.out.println(0);
            return;
        }

        solveBruteForce();

        System.out.println(ans);
    }

    private static void init() throws Throwable {
        final BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in), 1<<10
        );

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

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

        if (M > 0) {
            final StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            for (int mi = 0; mi < M; mi++) {
                final int brokenNumber = Integer.parseInt(st.nextToken());

                broken[brokenNumber] = true;
            }
        }

        br.close();
    }

    // +, - 버튼으로 정답에 가본다.
    private static void solveFirst() {
        ans = Math.abs(100 - target);
    }

    // 주어진 버튼들로 정답을 다 만들어본다.
    private static void solveBruteForce() {
        pick(1, 0);
    }

    private static void pick(int n, final int current) {
        // 500,000 까지 이므로
        // 최대 6자리까지만 숫자를 만들어 보면 된다.
        if (n > 6) {
            return;
        }

        for (int num = 0; num < 10; num++) {
            if (broken[num]) {
                continue;
            }

            final int nextCurrent = current * 10 + num;

            ans = Math.min(ans, Math.abs(target - nextCurrent) + n);
            pick(n + 1, nextCurrent);
        }
    }
}