[백준 Java] 1107번 리모컨

💡문제

[Gold V] 리모컨 - 1107

문제 링크

성능 요약

메모리: 11696 KB, 시간: 96 ms

---

🤔접근법

주어진 M 개 숫자들을 제외하고 0 ~ 9까지의 숫자들과 +1, -1 연산을 사용하여 숫자 100에서 N으로 가기 위해 이동 해야 하는 최소 횟수를 구하는 문제

범위 체크 및 시간복잡도 예상

• 0 ≤ N ≤ 500,000
• 0 ≤ M ≤ 10

풀이법

⭕ 접근 방법. 백트래킹

만약 시작점이 0이라면

고장나지 않은 숫자 버튼을 이용해 목표 채널까지 도달 할 수 있는 가장 가까운 채널로 이동 먼저 한 후 +1 , -1 둘 중 하나의 버튼 만을 이용해 쭉 이동하여 목표채널에 도달하는 게 가장 짧은 횟수로 이동하는 방법이다.

그러나 문제에서는 시작점이 100이기 때문에 숫자 버튼을 이용해서 가장 가까운 채널로 이동 후 움직이는 것보다 100에서 바로 움직이는 게 더 짧은 횟수를 가질 수도 있다. (ex) 99로 이동할때 9버튼이 고장난 경우

그래서 100에서 부터 목표 채널까지의 거리(+1 또는 -1로만 이동하는 횟수)를 먼저 고려한 후

도달 할 수 있는 모든 채널을 탐색하여 최소 버튼 사용 횟수를 비교하여 최소인 값을 출력한다.

탐색 범위는 가장 큰 목표 채널의 번호는 500,000 이기 때문에 1,000,000 -100 까지만 탐색하면 된다.

그 이유는 500,000이 목표 채널이라고 할 때 100에서 +1로 올라가 목표 채널 까지 이동하는 횟수와 1,000,000 - 100 에서 -1 로 내려 와 목표 채널까지 이동 횟수가 동일하기 때문이다.

목표 채널이 최대 500,000 일때 이동 횟수가 500,000-100보다 더 커지는 경우는 없기 때문에 1,000,000 그 이상의 채널에서 +1, -1로 이동해서 내려오는 경우는 생각하지 않아도 된다.

그러나 999,900 과 999,999 의 시간 복잡도는 크게 차이나지 않기 때문에 탐색 범위를 999,999로 생각하자.

그렇기 때문에 최대 탐색 숫자는 999, 999 이고 숫자 버튼을 누를 수 있는 횟수는 최대 6번이기에 종료조건은 숫자 버튼을 6번 눌렀을 경우 이다.

1. 0 ~ 999,999 까지 만들 수 있는 모든 숫자를 만드는데 단, 고장난 버튼의 숫자는 포함하지 않도록 한다.
2. 만든 번호의 채널에서 목표 채널까지의 거리(+1 또는 -1로만 이동하는 횟수)와 지금까지 누른 버튼 횟수(숫자 버튼으로 이동한 횟수)을 합하여 최소 값을 갱신한다.

➡️ 해당 풀이법의 시간 복잡도 : $O(N^6)$

---

😎SUCCESS

단박에 성공하지 못한 이유는 ?

기존 코드 ( 매우 지저분하니 보지 말자.. )

private static void makeChannel(int depth, int click) {
        if(click >= min) return;
        if(depth == 6){
            if(channel == 0){
                if(isBroken[0]) return;
                click +=1;
            }
            min = Math.min(min, click+Math.abs(N - channel));
            return;
        }
        for (int i = 0; i < 10; i++) {
            if(i != 0 && isBroken[i]) continue;
            if(i == 0 && isBroken[0]){
                if(channel != 0) continue;
            }
            channel = channel*10 +i;
            if( N > 100 && channel>N*2){
                break;
            }
            makeChannel(depth+1, channel == 0 ? 0 : click+1);
            channel = channel/10;
        }
    }

• 숫자 버튼을 무조건 6개를 누른 후에 숫자 버튼을 누른 횟수와 +/-로 이동하는 횟수를 고려했기 때문이다.
• 이렇게 할 경우 000001 같은 경우는 사실 숫자버튼을 1만 눌러도 이동할 수 있는 경우이기 때문에 앞에 붙어 있는 0을 제외 시키고 클릭 횟수를 다시 계산해야 하며 만약 0이 고장났을 경우에는 이동하지 못하는 채널이 되어 버린다.
• 이 경우들을 처리하느라 if 문이 상당히 많아지고 지저분해졌다.
• 이를 해결할 수 있는 방법은 버튼을 6개를 다 누르지 않고 한 개만 더 추가해서 눌러도 새로운 채널 번호가 만들어지는 것이기 때문에 재귀로 들어가기 전에 최소값을 갱신할 수 있는지 확인해주기만 하면된다.

---

👩‍💻 코드

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

public class Main_1107 {
    // N: 수빈이가 이동하려는 채널
    static int N;
    // M: 고장난 버튼의 개수
    static int M;
    // isBroken: 버튼이 고장났는지 여부를 저장하는 배열
    static boolean isBroken[];
    // min: 버튼을 최소 몇 번 눌러야 하는지를 저장하는 변수
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 수빈이가 이동하려는 채널을 입력 받음
        N = Integer.parseInt(br.readLine());
        // 고장난 버튼의 개수를 입력 받음
        M = Integer.parseInt(br.readLine());

        // 버튼이 고장나지 않은 경우를 기본으로 설정
        isBroken = new boolean[10];
        // 만약 고장난 버튼의 개수가 0이 아니라면,
        if (M != 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            // 고장난 버튼들을 입력 받아 isBroken 배열에 표시
            for (int i = 0; i < M; i++) {
                isBroken[Integer.parseInt(st.nextToken())] = true;
            }
        }

        // 현재 채널에서 목표 채널까지의 +1, 또는 -1 로만 이동하는 횟수
        min = Math.abs(N - 100);
        // 가능한 모든 채널을 탐색하여 최소 버튼 누름 횟수 갱신
        makeChannel(0, 0);
        // 최소 버튼 누름 횟수 출력
        System.out.println(min);
    }

		// click 번 버튼을 입력하여 channel 번호를 만드는 함수
    private static void makeChannel(int click, int channel) {
        // 종료 조건: 숫자 버튼을 6번 눌러 채널이 999,999를 넘어가면 종료
        if (click == 6) {
            return;
        }
        // 0부터 9까지 버튼을 하나씩 눌러가며 탐색
        for (int i = 0; i < 10; i++) {
            // 만약 해당 버튼이 고장났다면 스킵
            if (isBroken[i])
                continue;

            // 현재 채널 번호에서 1 ~ 9 까지 수 중 고장나지 않은 버튼을 추가로 눌러서 새 채널 번호를 만듦
            int newChannel = channel * 10 + i;
            // 목표 채널의 두 배보다 큰 채널은 탐색하지 않음
            // 목표 채널의 두배보다 더 크게 되면 100에서 +1, -1로 이동해 목표채널로 가는게 무조건 더 짧기 때문이다.
            if (N > 100 && newChannel > N * 2) {
                break;
            }

            // 현재까지 버튼을 누른 횟수와 목표 채널까지의 거리를 계산하여 최소값 갱신
            // Math.abs(N - newChannel) 는 +1, -1 버튼으로 이동한 횟수
            min = Math.min(min, (click + 1) + Math.abs(N - newChannel));
            // 새로운 채널로 재귀 호출하여 버튼을 누르는 과정을 반복
            makeChannel(click + 1, newChannel);
        }
    }
}