백준 1107번 : 리모컨 [자바]

 

 

 

🧫 문제 분석

✔️ 출처

리모컨 골드 5

 

📖 문제

 

부서진 버튼을 제외한 버튼들을 가지고 

BackTracking으로 완전탐색해서 이동하려는 채널 길이와 가장 가까운 수를 찾는다. 

이동하려는 채널 길이 - 1 ~ 이동하려는 채널 길이 +1 까지의 수를 찾는데 

그 이유는 998 < 999 < 1000 이런 느낌의 수가 나올 수 있기 때문이다. 

 

이문제 15% 와 32%에서 계속 틀렸었다.

 

15% 실패

처음 백트래킹 메서드를 호출할때 매개변수로 깊이를 0, 숫자를 0으로 줘서 

n = 1 이고

0버튼이 부숴졌다고 했을 때 

매개변수로 시작 숫자를 0으로 줘서 버튼이 부숴졌음에도 불구하고 

if문에 걸려 바로 최솟값으로 반환되버렸다.

 

 

32% 실패

단순 Math.abs(n - 탐색으로 찾은 수) < min 이면 min = Math.abs(n - 탐색으로 찾은 수), len = 현재 num의 길이

이런식으로 구하고

탐색이 끝나고 나서 min + len으로 반환했는데 이게 잘못되었다.

        //  size보다 1작은 길이의 숫자 혹은 길이가 1큰 숫자도 고려해야함
        if (size - 1 <= depth && depth <= size + 1) {
            if (Math.abs(num - target) < min) {
                min = Math.abs(num - target);
                len = String.valueOf(num).length();
            }
        }

버튼 길이와 +-로 이동하는 Math.abs(n - 탐색으로 찾은 수) < min 으로 비교해서 

min의 최솟값을 갱신해야한다. 

        if (size - 1 <= depth && depth <= size + 1) {
            int abs = Math.abs(num - target);
            int len = depth;
            min = Math.min(abs + len, min);

 

 

---

🔅 문제 풀이

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

class Main {
    static ArrayList<Integer> list = new ArrayList<>();
    static int min = 500001;

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

        String target = br.readLine();
        int n = Integer.parseInt(target);
        int m = Integer.parseInt(br.readLine());
        boolean[] brokenBtn = new boolean[10];

        // 부서진 리모컨이 있다면
        if (m > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < m; i++) {
                int idx = Integer.parseInt(st.nextToken());
                brokenBtn[idx] = true;
            }

            // 없다면 숫자버튼만으로 해결 가능  현재 위치 100에서 +-로 이동 vs 버튼만 눌러서 이동 최솟값이 정답
        } else if (m == 0) {
            System.out.println(Math.min(target.length(), Math.abs(100 - n)));
            return;
        }

        // 리스트에 부서지지 않은 버튼 숫자를 저장
        for (int i = 0; i < 10; i++) {
            if (!brokenBtn[i]) {
                list.add(i);
            }
        }

        // 부서지지 않은 버튼 숫자를 시작으로 완전탐색 시작
        for (int i : list) {
            backTracking(n, 1, target.length(), i);
        }

        System.out.println(Math.min(Math.abs(100 - n), min));
    }


    private static void backTracking(int target, int depth, int size, int num) {

        // size +2 는 범위를 벗어나므로 종료
        if (depth == size + 2) return;

        //  size보다 1작은 길이의 숫자 혹은 길이가 1큰 숫자도 고려해야함
        if (size - 1 <= depth && depth <= size + 1) {
            int abs = Math.abs(num - target);
            int len = depth;
            min = Math.min(abs + len, min);
            /**
             * 기존 코드 32퍼 실패 이유
             * (숫자 버튼을 누르는 횟수 + (+1 - 1)로 이동하는 횟수)와 기존 최솟값을 비교하지 않았기 때문
             *
             */
        }

        for (int n : list) {
            backTracking(target, depth + 1, size, num * 10 + n);
        }
    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.  어려웠다. 생각할게 많았고, 범위 체크, 깊이가 1인 n 입력, n 보다 길이가 더 긴 수와 더 작은 수의 최솟값 고려 등등.. 쉽지않다.