BOJ 1107 리모컨

문제 풀이 방식

• 0~999,999(500,000 의 경우 해당 자리수의 최대값이 999,999)까지 모든 경우의 수를 검사한다. -> Brute Force
• 변수를 갱신해가며 최솟값을 찾는다.
• 참고한 풀이

문제 풀이 (Java)

import java.io.BufferedReader;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
  
public class boj1107 {  
    static int N, M;  
    static long cnt;  
    static boolean[] isBroken = new boolean[10];  
    public static void main(String[] args) throws Exception {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
  
        N = Integer.parseInt(st.nextToken());  
        st = new StringTokenizer(br.readLine());  
        M = Integer.parseInt(st.nextToken());  
  
        for(int i = 0; i < 10 ; i++){  
            isBroken[i] = false;  
        }  
  
        // 고장난 버튼 저장  
        if(M != 0) {  
            st = new StringTokenizer(br.readLine());  
        }  
        for(int i = 0; i < M ; i++){  
            int tmp = Integer.parseInt(st.nextToken());  
            isBroken[tmp] = true;  
        }  
  
        int res = Math.abs(N - 100); // +, - 만으로 이동할때의 값으로 초기화  
  
        // 0부터 1000000까지 모든 채널 순회해서 제일 적은 버튼 눌러 이동하는 값 찾기  
        for(int i = 0; i < 1000000 ; i++){  
            // 숫자버튼을 이용해서 이동이 가능한지, 가능하다면 몇 번의 버튼을 누르는지 구한다.  
            int len = possible(i);  
            if (len > 0) {  
                // + 또는 -를 몇 번 눌러야 하는지 구하는 변수
                int press = Math.abs(i - N);  
                
                if (res > len + press) {  
                    res = len + press;  
                }  
  
            }  
        }  
  
  
        System.out.println(res);  
    }  
  
    private static int possible(int i) {  
        if (i == 0) {  
            // 예외처리  
            if (isBroken[0]) {  
                return 0;  
            } else {  
                return 1;  
            }  
        }  
  
        int len = 0;  
  
        while (i > 0) {  
            // 고장 여부를 확인한다.  
            if (isBroken[i % 10]) {  
                return 0;  
            }  
            len += 1;  
            i /= 10;  
        }  
        return len;  
    }  
}