백준 1107번 리모컨: 입력 가능한 채널을 모두 비교하기

숫자 입력과 채널 이동을 나눠 봅니다

처음 채널은 100번입니다. 숫자 버튼을 누르지 않고 +, -만 쓰면 Math.abs(N - 100)번 눌러야 합니다. 목표가 4000번이고 숫자 버튼이 모두 고장 났다면 3900번입니다. 이 값을 먼저 답의 후보로 두었습니다.

다음으로 0부터 999999까지 숫자로 입력할 채널을 하나씩 확인합니다. 입력할 수 있는 채널이라면 숫자 버튼을 누른 횟수 + 목표 채널까지의 거리를 계산해서 기존 답보다 작을 때만 답을 바꿉니다. 목표와 가까운 채널이 꼭 답이 되지는 않습니다. 숫자 입력까지 합친 횟수를 비교해서 가장 작은 채널을 찾습니다.

고장 난 버튼은 배열로 확인합니다

broken[숫자]가 true이면 고장 난 버튼입니다. 그래서 후보 채널의 각 자릿수를 확인할 때 고장 난 버튼 목록을 다시 순회하지 않아도 됩니다.

당시에는 고장 난 버튼을 반복문으로 찾으면 반드시 시간 초과가 난다고 생각했습니다. 하지만 버튼은 최대 10개이므로 반복문을 쓴다는 사실만으로 시간 초과를 단정할 수는 없습니다.

n % 10으로 일의 자리를 얻고 n /= 10으로 그 자리를 지웁니다. check()는 모든 버튼을 쓸 수 있으면 자릿수를, 고장 난 버튼이 있으면 0을 반환합니다. 채널 0은 반복문에 들어가지 않으므로 버튼 0을 한 번 누르는 경우를 따로 처리했습니다.

당시 제출 코드

Java

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

class Main {

    static int N, M;
    static boolean[] broken;

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

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        broken = new boolean[10];

        if (M != 0) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < M; i++) {
                broken[Integer.parseInt(st.nextToken())] = true;
            }
        }


        int result = Math.abs(N - 100);
        for (int i = 0; i < 1000000; i++) {
            if (check(i) != 0) {
                result = Math.min(result, Math.abs(N - i) + check(i));
            }
        }
        bw.write(String.valueOf(result));
        bw.flush();
    }

    public static int check(int n) {
        if (n == 0) return broken[0] ? 0 : 1;

        int cnt = 0;

        while (n > 0) {
            if (broken[n % 10]) return 0;

            n /= 10;
            cnt++;
        }
        return cnt;
    }
}