[알고리즘_풀이] 백준 1107, 리모컨

문제 요약

숫자(0-9), '+', '-' 버튼으로 이루어진 리모컨으로 원하는 채널로 이동 하고 싶다.

단, 숫자 누르는 버튼(0-9) 중, 고장난 버튼이 주어진다.

 

input 값 : N, M, 고장난 숫자 버튼

output 값 : 버튼(숫자, +, - 버튼)을 총 몇번 눌러야하는지. 

100번 -> N

현재 채널 : 100번

이동하려고 하는 채널 : N

고장난 숫자 버튼의 수 : M

고장난 숫자 버튼 : B1, B2, .... ,  Bn (M개) 

 

해결 전략

1. 고장나지 않은 버튼을 이용해 숫자로 이동할 수 있는 채널(c)을 구한다. c를 구하면 길이를 반환하면 된다

   -> 'len'

   -> 0-500000까지 for-loop로 하나씩 맞는지 확인한다.

 

2. 이동할 채널(C)와 원래 이동하려고 했던 채널(n)의 차이값(절댓값을 구하면 된다.)으로 '-' 혹은 '+'로 이동해야 할 숫자를 구한다.

  -> 'press'  

 

3. 그 이동 값이 최소인지 확인한다.

  처음에 ans = 목표채널(n) - 100;을 넣어둔다.

  ans과 (숫자버튼으로 이동) + ('-' 혹은 '+'버튼으로 이동)을 비교해서 더 작은 값을 출력하면 된다.

 

 

java 코드

import java.util.Scanner;

public class backjoon_1107 {
    static boolean[] checknotWorking = new boolean[10]; //0-11, true ? 쓸 수 없다는 뜻 : ""
    static int possible(int c){
        if(c == 0) {
            if(checknotWorking[0]) {
                return 0;
            }else {
                return 1;
            }
        }

        int len = 0;
        while(c > 0){
            if(checknotWorking[c%10]){
               return 0;
            }
            len += 1;
            c /= 10;
        }

        return len;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 이동하려는 채널
        int M = sc.nextInt(); // 고장난 리모컨 개수

        int ans = N - 100;

        if (ans < 0) {
            ans = -ans; // n < 100
        }

        for(int i=0; i<M; i++){
            int tmpNum = sc.nextInt();
            checknotWorking[tmpNum] = true;
        }

        for(int i=0; i<=1000000; i++){
            int c = i;
            int len = possible(c);
            if(len > 0){
                int press = c - N;
                if(press < 0){
                    press = -press;
                }
                if(ans > press+len){
                    ans = press + len;
                }
            }

        }

        System.out.println(ans);


    }
}