백준 1107번 - 리모컨 (JAVA)

문제링크

 

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

 

 

문제 풀이 방법

숫자를 전부 눌러서 타겟 번호와 일치 할때 최소인 값을 찾는게 이 문제의 핵심이다.

 

3가지 경우로 나눠서 답을 도출해야한다.

 

1. 처음 타켓 번호가 100 일때는 0을 출력 한다. 그 이유는 현재 시청 중인 번호가 100이기 때문이다.

2. 현재 번호에서 + / - 으로만으로 타켓 번호까지 갈때의 경우

3. 최대한 근사치 번호까지 누른 다음 + / - 를 이용해서 타켓 번호에 도달 했을 때의 경우

 

2는 타겟 번호에서 현재 번호인 100을 뺐을 때의 수가 된다.

 

3번의 경우는 탐색을 이용하여 문제를 해결해야한다.

고장난 번호가 아닌 숫자를 이용하여 만든 숫자에서 타켓 번호까지 + / - 한 횟수를 더한 값 중에서 최소인 값으로 업데이트 해주면 된다.

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static boolean[] broken;
    static int target;
    static long count;
 
    public static void dfs(int idx, int click){
        for (int i = 0; i < 10; i++) {
            if(!broken[i]){
                int newBtn = click * 10 + i;
                int cnt = Math.abs(target - newBtn) + String.valueOf(newBtn).length();
                count = Math.min(count, cnt);
 
                if(idx < 6) {
                    dfs(idx + 1, newBtn);
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        target = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());
 
        broken = new boolean[10];
        if(n > 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                int cur = Integer.parseInt(st.nextToken());
                broken[cur] = true;
            }
        }
 
        if(target == 100){
            System.out.println(0);
            return;
        }
 
        count = Math.abs(target - 100);
 
        dfs(0, 0);
        System.out.println(count);
    }
}