1107번: 리모컨

문제

수빈이는 TV를 보고 있습니다. 수빈이의 리모컨에는 0부터 9까지의 숫자 버튼과 '+', '-' 버튼이 있습니다. 현재 채널은 100번입니다. 일부 숫자 버튼이 고장 나서 누를 수 없을 때, 수빈이가 원하는 채널 N으로 이동하기 위해 리모컨 버튼을 최소 몇 번 눌러야 하는지 구하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어집니다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어집니다. 셋째 줄에는 고장난 버튼이 주어집니다.
• 출력: 첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지 출력합니다.

링크: https://www.acmicpc.net/problem/1107

풀이: 0부터 999,999까지의 완전 탐색 (Brute Force)

이 문제를 해결하는 가장 안전하고 확실한 방법은, 우리가 누를 수 있는 모든 채널에 대해 버튼 누름 횟수를 계산해 보고 그 중 최솟값을 찾는 것입니다. 목표 채널 n의 최댓값은 500,000이지만, 예를 들어 500,000으로 갈 때 600,000을 누르고 - 버튼을 누르는 것이 더 빠를 수 있으므로 넉넉하게 1,000,000미만(0 ~ 999,999)의 모든 채널을 탐색합니다.

• 초기 최솟값 설정: 숫자 버튼을 아예 누르지 않고 현재 채널인 100번에서 +나 - 버튼만으로 이동하는 경우인 Math.abs(n - 100)을 최솟값(ans)으로 설정해 둡니다.
• 완전 탐색: 0번부터 999,999번 채널까지 반복문을 순회합니다.
  • check 메서드를 통해 해당 채널(i)을 고장나지 않은 버튼만으로 누를 수 있는지 확인하고, 누를 수 있다면 그 길이를 반환합니다.
  • 누를 수 있다면, 숫자 버튼을 누른 횟수(len) + 목표 채널까지 +/-로 이동하는 횟수(Math.abs(n - i))를 계산하여 기존 ans와 비교해 더 작은 값으로 갱신합니다.
• 효율적인 자릿수 추출 (check 메서드): 문자열 변환(i + "")을 사용하면 메모리 할당으로 인해 속도가 느려집니다. 이를 피하기 위해 % 10과 / 10 연산을 활용하여 정수형 상태 그대로 자릿수를 분리하고 검사함으로써 실행 시간을 극적으로 단축시켰습니다.

코드

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

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

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        boolean[] 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;
            }
        }

        // 1. 숫자 버튼 없이 + 또는 - 버튼만으로 이동하는 경우를 초기 최솟값으로 설정
        int ans = Math.abs(n - 100);
        
        // 2. 0부터 999,999번 채널까지 숫자 버튼으로 누르고 이동하는 모든 경우 탐색
        for (int i = 0; i < 1000000; i++) {
            int len = check(i, broken);

            // 해당 채널을 고장나지 않은 숫자 버튼으로 누를 수 있다면
            if (len > 0) {
                // (숫자 버튼 누르는 횟수) + (해당 채널에서 타겟까지 +/- 누르는 횟수)
                ans = Math.min(ans, len + Math.abs(n - i));
            }
        }

        bw.write(ans + "");
        bw.flush();
    }

    // 해당 채널을 누를 수 있는지 판별하고, 누를 수 있다면 버튼 누른 횟수(자릿수)를 반환하는 메서드
    static int check(int x, boolean[] broken) {
        // 0번 채널 예외 처리
        if (x == 0) {
            return broken[0] ? 0 : 1;
        }

        int len = 0;
        // 문자열 변환 대신 모듈러 연산으로 각 자릿수 분리 (속도 최적화)
        while (x > 0) {
            if (broken[x % 10]) {
                return 0; // 고장난 버튼이 포함되어 있으면 즉시 불가능(0) 반환
            }

            x /= 10;
            len++;
        }

        return len;
    }
}

알고리즘 분류

브루트포스 알고리즘 (Brute Force)