[백준] 1107번. 리모컨(JAVA)

문제

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

---

풀이(30분)

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

public class Main {
    static boolean[] breakdown = new boolean[10]; // 고장난 버튼 체크 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int target = Integer.parseInt(br.readLine()); // 이동하려는 채널
        int m = Integer.parseInt(br.readLine()); // 고장난 버튼 개수

        Arrays.fill(breakdown, true); // 모든 버튼을 정상 상태(true)로 초기화

        if (m != 0) { // 고장난 버튼이 있을 경우
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < m; i++) {
                breakdown[Integer.parseInt(st.nextToken())] = false; // 고장난 버튼 false 처리
            }
        }

        // 1. ± 버튼만 사용해서 이동하는 경우
        int minPress = Math.abs(100 - target);

        // 2. 숫자 버튼을 누르고 ± 버튼으로 이동하는 경우
        for (int i = 0; i <= 999999; i++) {
            int len = checkValid(i); // 숫자 i를 누를 수 있는지 확인하고, 길이 반환
            if (len > 0) {
                int press = len + Math.abs(i - target); // 숫자 버튼 누른 후 ± 버튼으로 이동하는 횟수
                minPress = Math.min(minPress, press);
            }
        }

        // 정답 출력
        System.out.println(minPress);
    }

    // 해당 숫자를 눌러서 이동할 수 있는지 확인하는 메서드
    static int checkValid(int num) {
        if (num == 0) return breakdown[0] ? 1 : 0; // 0만 누를 경우 예외 처리

        int len = 0;
        while (num > 0) {
            if (!breakdown[num % 10]) return 0; // 고장난 버튼이 포함되면 불가능
            num /= 10;
            len++;
        }
        return len;
    }
}

---

문제 풀이 전략

 

문제를 처음 접했을 때 같은 자릿수 내에서의 위아래의 근사치, 자릿수가 클 때와 작을 때의 위아래의 근사치 총 4개의 값을 가지고 비교를 하려고 했다. 물론 틀린 아이디어는 아닌 것 같으나 구현에 있어 문제가 있었고, 문제를 다시 살펴봤다.

 

문제에서 제시된 n(채널)의 범위는 50만까지였고, 모든 숫자버튼이 고장난 경우에 대해 생각해도 100만 번의 반복만 하면 되는 문제였다.

즉, 브루트포스로 해결할 수 있는 것이다.

왜냐하면 한번의 채널에 대해 커야 6 자릿수에 대해 true/false 연산을 진행하면 되고, 이에 따라 정답과 비교를 위한 연산 총 7번의 연산이 최대였다.

대략적으로 700만번의 계산 안에서 해결할 수 있는 문제이기 때문에 완전탐색을 통해 해결했다.

 

문제를 잘 살펴보면 완전탐색도 좋은 풀이가 될 수 있다.