[백준] 1107번: 리모컨 (Java)

문제

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

난이도 : 골드5

알고리즘 : 브루트포스

---

풀이 과정

0부터 9까지 숫자와 +, - 버튼이 있는 리모컨이 있다. 지금보고 있는 100번 채널에서 수빈이가 원하는 채널로 이동하기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 문제다.

 

원하는 채널로 이동하는 방법은 여러가지다.

먼저, +, - 버튼만을 눌러서 이동할 수 있을 것이다. 또한, 숫자 버튼을 사용하여 원하는 채널의 번호를 입력하여 바로 이동할 수도 있다. 이 때, 숫자 버튼이 고장났을 수도 있기 때문에 원하는 채널로 바로 이동할 수 없는 경우도 있다. 그렇기 때문에 숫자 버튼을 사용하여 다른 채널로 이동한 뒤에 +, - 버튼을 사용하여 원하는 채널로 이동하는 경우를 고려해야 한다.

이동하려고 하는 채널 N의 범위가 0 ≤ N ≤ 500,000 이므로, 숫자 9만 누를 수 있는 경우를 고려하여 0번부터 999,999번까지 채널을 거쳐서 원하는 채널로 가는 방법을 계산하면 된다.

 

이동 횟수의 초기값은 +, -  버튼만으로 이동하는 경우, 즉 |N - 100|으로 설정한다.

 

먼저, 0부터 999,999까지의 숫자들에 대해 한 자리씩 탐색하며 고장난 버튼의 번호를 포함하고 있는지 검사한다. 

 

만약 고장난 버튼의 번호를 포함하는 채널이라면, 이동할 수 없으므로 다음 채널로 넘어간다.

숫자 버튼으로 이동할 수 있는 채널이라면, 이동 횟수는 (채널번호의 길이 + |N - 채널번호|)가 된다. 

이렇게 구한 이동 횟수가 기존의 이동 횟수보다 작으면 새로운 값으로 갱신한다. 이러한 과정을 반복하면, 정답을 얻을 수 있다.

 

---

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        boolean[] broken = new boolean[10];
        if(m > 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0;i<m;i++){
                broken[Integer.parseInt(st.nextToken())] = true;
            }
        }

        int min = Math.abs(n - 100);
        for(int i=0;i<=999999;i++){
            String rawNum = String.valueOf(i);
            boolean check = false;
            for(int j=0;j<rawNum.length();j++){
                if (broken[rawNum.charAt(j) - '0']) {
                    check = true;
                    break;
                }
            }
            if(check) continue;

            int count = rawNum.length() + Math.abs(n - i);
            min = Math.min(min, count);
        }

        System.out.print(min);
    }
}