[백준] 리모컨 : 1107 - 완전 탐색 (G5)

1.  💎 문제

1107번: 리모컨

 

 

 

---

 

2.  🤔 어떻게 풀까?

이 문제의 핵심은 주어진 번호들로 얼마나 근사치를 만들 수 있느냐이다. 고민을 많이 했다가 생각난 방법이 그리디였다. 자릿수마다 가장 크기 차이가 안나는 수를 선택하는 작업을 반복한다. 만약 주어진 수가 `54321`이라면 가장 첫 번째 수인 5와 가장 가까운 수를 망가지지 않은 버튼들에서 찾는다. 모두가 망가지지 않았다면 4와 6일 것이다.

 

하지만 여기서 4와 6중 무엇을 선택해야 할까? 나는 여기서 다음 자리 수를 비교하는 작업을 더 했다. 여기부터 슬슬 이상함이 감지되었다. 만약 또 크기 차이가 같다면? 다시 반복을 해야되는 것인가. 그러면 DFS를 써볼까? 흠 아닌 것 같은데,,  그냥 중복은 한 번만 체크하고 넘어가기로 했다.. 이렇게 어거지로 구현은 다 했지만 역시 테스트 케이스에서 오답이 나왔다.

 

내가 짠 코드는 80000이 원하는 수로 주어지고 8,9가 망가진 버튼으로 주어질 때, 가장 근차시로 70000를 만든 후 만을 더해줬다.. 각 자릿수마다 비교하다 보니 두번째 자리인 0을 비교할 때 클릭할 수로 0을 택한 것이다. 여기서 이제 선택을 할 때마다 그 수를 빼줘서 다시 작업을 해야할까? 다 아닌 것 같다.. 포기

 

 

 

 

3. 💡 해결 로직

사실 이 문제는 차이의 최솟값이 최선이 아닐 수 있다는 전제가 있다. (참고) https://www.acmicpc.net/problem/1107 

그래서 애초에 그리디로 접근하면 안된다고 한다. 이 문제는 바로 완전 탐색을 해서 최선의 수를 구하는 것이다.

입력을 보면 크기의 조건이 크기 않다. 어떻게 해서든 최댓값은 500,000이다. 또한 자릿수에 대해서 비교가 일어나므로, 주어진 답이 최댓값인 500,0000이라 할지라도 9의 7승으로 478,2969 번의 연산이면 찾을 수 있다.

 

DFS 탐색을 진행해서 자릿수마다 값을 결정 후 누적된 값으로 다시 DFS를 호출한다. 이때 선택된 수가 6개를 넘어가면 탐색을 종료한다.

idx는 선택이 완료된 숫자의 길이를 나타내고, clicked는 누적된 값이다. 

  public static void dfs(int idx, String clicked){
        for(int i=0; i<isBroken.length; i++){
            if(isBroken[i]) continue;

            String newStr = clicked + Integer.toString(i);
            // 숫자를 만들고 빼봤을 떄 더 작은거
            int cnt = Math.abs(currentNum - Integer.parseInt(newStr)) + newStr.length();
            min = Math.min(cnt, min);
            // 최대가 6자리이므로
            if(idx < 6) {
                dfs(idx+1, newStr);
            }
        }
    }

 

 

 

4.  ⭐️ 배운 점

1.  각 자릿수에 접근하는 방법을 String 으로

이때까지 나는 String의 charAt 방법을 써서 구한 다음에 다시 맞는 자릿수 만큼 10을 거듭제고 해서 더하는 것을 반복했다.

하지만 할 때마다 불편했는데 , 위의 방법처럼 String으로 수를 처리하면 간단한 것 같다!!

 

더해주는 작업을 단지 `"123" + "3`로 해주기만 하면 된다. 

 

 

2. 완전 탐색 방법도 있구나

입력의 조건을 생각 안하고 무조건 빠르게 풀 수 있는 방법이 정답이겠지 생각하고 모두를 탐색한다는 것을 생각 못했다.

하지만 이번 문제처럼 지금의 방법이 최선이 아닐 수도 있을 때, 모두 탐색해도 시간이 오래걸지 않을 때는 무조건 완전 탐색을 고려 해야한다.

 

 

 

5. 🖥️ 코드

import java.io.*;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    static int currentNum;
    static long min;
    static boolean [] isBroken;
    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 strNum =br.readLine();
        currentNum = Integer.parseInt(strNum);
        int brokenCount = Integer.parseInt(br.readLine());
        isBroken  = new boolean[10];

        if(brokenCount != 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0; i< brokenCount; i++){
                int n = Integer.parseInt(st.nextToken());
                isBroken[n] = true;
            }
        }

        // 타겟이 100번인 경우
        if(currentNum == 100){
            System.out.println("0");
            return;
        }


        // 망가지지 않은 수 넣기
        HashSet<Integer> nums = new HashSet<>();
        for(int i=0; i<9; i++){
            if(!isBroken[i])
                nums.add(i);
        }

        currentNum = Integer.parseInt(strNum);
        // 100번 채널에서 +, -로만 이동
        min = Math.abs(currentNum - 100);

        dfs(0, "");
        bw.write( min+ "\n");

        bw.flush();
        bw.close();
        br.close();
    }

    public static void dfs(int idx, String clicked){
        for(int i=0; i<isBroken.length; i++){
            if(isBroken[i]) continue;

            String newStr = clicked + Integer.toString(i);
            // 숫자를 만들고 빼봤을 떄 더 작은거
            int cnt = Math.abs(currentNum - Integer.parseInt(newStr)) + newStr.length();
            min = Math.min(cnt, min);
            // 최대가 6자리이므로
            if(idx < 6) {
                dfs(idx+1, newStr);
            }
        }
    }

}