[백준 1107번 / Java] 리모컨 - Brute Force(DFS)

문제 링크

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

1107번: 리모컨

 

 

---

 

 

풀이

1. 500,000까지의 채널이 존재했고, 가장 큰 경우가 999,999의 경우를 고려하여 반복문의 최대 길이를 설정

2. answer는 단순 +,-로 해당 채널로 이동하는 경우, 버튼을 눌리는 횟수

3. length는 해당 버튼의 길이. 즉 해당 채널로 이동하기 위한 버튼을 눌리는 횟수

4. 모든 경우의 수에서 최소값을 구함

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

public class BaekJoon1107 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int channel = Integer.parseInt(br.readLine());
        int brokenBtn = Integer.parseInt(br.readLine());
        int[] brokenBtnArr = new int[10];

        if(brokenBtn > 0){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int i = 0; i < brokenBtn; i++) {
                int number = Integer.parseInt(st.nextToken());
                brokenBtnArr[number]--;
            }
        }
        
        if(channel - 100 == 0) {
            System.out.println(0);
            return;
        }

        //+- 눌려서 이동하는 거리
        int answer = Math.abs(channel - 100);
        StringBuffer sb = new StringBuffer();

        for(int i = 0; i < 1000000; i++) {
            sb.append(String.valueOf(i));
            int length = sb.length();
            boolean chk = false;

            for(int j = 0; j < length; j++) {
                if(brokenBtnArr[sb.charAt(j) - '0'] == -1) {
                    chk = true;
                    break;
                }
            }

            if(!chk) {
                //+-이동과 버튼 눌렸을 때의 합
                answer = Math.min(Math.abs(channel - i) + length, answer);
            }

            sb.setLength(0);

        }

        System.out.println(answer);

    }

}