백준 1107 리모컨

문제

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

---

입출력

---

예제

---

태그

• 브루트포스 알고리즘

---

풀이

• 완전탐색 - dfs를 이용
• N의 최대값 : 500,000이므로 6자리가 최대이다.
• 0~9까지 depth가 6, 즉 10^6은 1억이 안되므로 완전탐색을 사용한다.
• 주어진 N = 100이면 답은 0이다.
• 완전탐색으로 구한 최소값보다 100번에서 +, - 버튼으로만 이동 가능한 최솟값이 더 작으면 이것이 답이다. -> 이를 놓쳐서 시작하자마자 틀렸다.
• 0~9까지 누를 수 있는 버튼을 하나씩 String 변수에 더하고 그 값과 주어진 N값을 비교 후 최솟값을 구한다.

---

코드

정답 코드

/**
 * 1107_리모컨
 * 
 * 완전탐색 - dfs를 이용
 * N의 최대값 : 500,000, 즉 6자리가 최대이다.
 * 0~9까지 depth가 6, 즉 10^6은 1억이 안되므로 완전탐색을 사용한다.
 *
 * 주어진 N = 100이면 답은 0
 * 완전탐색으로 구한 최소값보다 100번에서 +, - 버튼으로만 이동 가능한 최솟값이 더 작을 경우 이것이 답
 */

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

public class P_1107 {

    static int N, M;
    static boolean[] wrongNums = new boolean[10]; // 0~9중 고장난 버튼은 true
    static int min = Integer.MAX_VALUE; // 출력할 답
    static String change = ""; // 고장난 버튼이 아닌 경우 완전탐색을 돌면서 추가할 숫자를 적을 변수

    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());
        StringTokenizer st;

        // 고장난 버튼이 있으면 그 버튼에 해당하는 index 값을 true
        if(M > 0){
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++) {
                wrongNums[Integer.parseInt(st.nextToken())] = true;
            }
        }

        // N = 100이면 버튼을 누를 필요가 없다.
        if(N == 100){
            min = 0;
        }

        // min값을 구한다.
        dfs(change, 0);

        // 완전탐색으로 구한 min 값과 100번에서 +, -로만 버튼을 누르는 경우를 비교한다.
        int cnt = Math.abs(100 - N);
        if(min > cnt){
            min = cnt;
        }

        System.out.println(min);

    }

    static void dfs(String str, int depth) {
        // N의 최대 자리수는 6이므로 탐색 깊이가 6이면 return
        if(depth == 6){
            return;
        }

        for (int i = 0; i < 10; i++) {
            // 버튼이 고장나지 않았다면
            if (!wrongNums[i]) {
            	// 숫자를 하나씩 채워준다.
                change = str + i;
                min = Math.min(min, calculate(change, N));
                dfs(change, depth+1);
            }
        }

    }

    // 버튼 누르는 횟수 계산 메서드
    static int calculate(String str, int n) {
        return Math.abs(n - Integer.parseInt(str)) + str.length();
    }
}