[Java] 백준(골드-5) 1107번 - 리모컨

문제 풀이

---

이번 문제는 완전 탐색을 이용해 풀 수 있는 문제이다.

아이디어 도출

문제 그대로 고장난 버튼을 제외한 숫자 버튼으로 N 채널로 이동하기 위한 최소 버튼 클릭 횟수를 구해야 한다.

어떻게 버튼 클릭 횟수를 구할 수 있을까? 예제를 살펴보자.

5457
3
6 7 8
누를 수 있는 리모콘 번호: 0, 1, 2, 3, 4, 5, 9

5455 버튼까지 4번을 누른 후, 5457 버튼까지 +버튼을 2번 누르면 5457 채널로 이동할 수 있다. 이 때 버튼을 누른 횟수는 총 6번이다.

또 다른 예시를 보자.

1555
8
0 1 3 4 5 6 7 9
누를 수 있는 리모콘 번호: 2, 8

888 버튼까지 3번을 누른 후, 1555번 채널까지 +버튼을 667번 누르면 1555번 채널로 이동할 수 있다.

결국 이와 같이 최소 버튼 클릭 횟수를 구할 아이디어는 다음과 같다.

1. 이동할 채널(N)이 100이라면 현재 채널이 0이기에 0번을 출력한다.
2. 이동할 채널(N)이 100이 아니라면, N의 범위만큼 완전탐색하며 최소로 클릭되는 횟수를 구한다.
3. N의 범위는 500,000이지만, 9를 제외한 모든 버튼이 고장나는 경우를 대비해 999,999까지 확장하여 연산한다.
4. N과 유사한 버튼까지 누른 후, +버튼이나 -버튼 횟수가 추가된 값과 비교해가며 최소 버튼 클릭 횟수를 구한다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

import java.io.*;

class Main {    

    public static void main(String[] args) throws IOException {

        /**
         * 현재 채널은 100이다.
         * 1. N이 100이라면, 바로 0을 출력한다.
         * 2. 100에서 +나 -버튼만으로 N을 만들 경우엔 N에서 100을 차감한다.
         * 3. N과 가장 가까운 번호를 누른 후, +나 -버튼으로 N을 만들 경우 완전탐색을 해야 한다.
         */

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // 이동할 채널 N
        int N = Integer.parseInt(br.readLine());
        
        // 고장난 리모컨 버튼 개수 M
        int M = Integer.parseInt(br.readLine());
        
        // 고장난 리모컨 버튼 위치를 기록할 배열
        boolean[] broken = new boolean[10];
        
        if(M > 0) {
            // 고장난 리모콘 위치 갱신
            String[] brokens = br.readLine().split(" ");
            for(int i=0; i<brokens.length; i++) {
                int idx = Integer.parseInt(brokens[i]);
                broken[idx] = true;
            }
        }

        // +나 -버튼으로만 N 채널로 이동할 경우를 먼저 갱신
        int result = Math.abs(N - 100);

        // N의 범위는 500,000이지만
        // 리모콘을 999999 버튼을 눌러서 찾는 경우도 있기 때문에 최대값을 6자리로 확장한다.
        for(int i=0; i<=999999; i++) {
            
            // 현재 누른 숫자
            String num = String.valueOf(i);

            // 고장난 버튼을 하나라도 누르면 안되기에 탐색을 종료 한다.
            boolean isBroken = false;
            for(int j=0; j<num.length(); j++) {
                if(broken[num.charAt(j) - 48]) {
                    isBroken = true;
                    break;
                }
            }

            // i 버튼을 눌렀을 때, 고장난 버튼이 아닌 정상 버튼들만 눌렀을 경우
            if(!isBroken) {
                // i를 누른 후 N 버튼을 누르기까지의 횟수 중 최소 횟수를 result에 기록한다.
                int cnt = Math.abs(N - i) + num.length();
                result = Math.min(cnt, result);
            }

        }

        bw.write(result+"\n");
        
        bw.close();
        br.close();
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.