[BOJ] 백준 1107번: 리모컨

문제

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

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

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

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

 

풀이

이 문제를 처음 접근했을 때 각 자리수 별로 고장이 안난 가장 가까운 수로 숫자를 가져와 숫자를 만들고 해결하는 방법을 생각했지만 예외사항이 너무 많았습니다 ex) 80000의 경우 77777이 나와야하는데 70000이 나오는 케이스가 발생했습니다.

따라서 리모콘이 9까지 있으므로 브루트포스를 통해 0~999999까지 모든 케이스를 생각하고 그 중 고장난 숫자가 포함되지 않은 숫자의 값을 가져와 Math.min을 적용하여 해결하였습니다.

 

코드

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int N, M;
    static boolean[] breakdown = new boolean[10];

    static void input() throws IOException{
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        if(M != 0){
            st = new StringTokenizer(br.readLine());
            for(int i=0; i<M; i++) breakdown[Integer.parseInt(st.nextToken())] = true;
        }
    }

    static void process(){
        int ans = pressPMBtn(100);

        for(int i=0; i<1000000; i++){
            String numStr = String.valueOf(i);
            if(!isBroken(numStr)){
                ans = Math.min(ans, pressPMBtn(i)+numStr.length());
            }
        }
        System.out.println(ans);
    }

    private static boolean isBroken(String numStr) {
        for(int i=0; i<numStr.length(); i++)
            if(breakdown[numStr.charAt(i)-'0']) return true;
        return false;
    }

    static int pressPMBtn(int num){
        return Math.abs(N-num);
    }

    public static void main(String[] args) throws IOException{
        input();
        process();
    }
}

 

 

<출처>

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