[1107] 리모컨

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

보고 싶은 TV 채널 N이 주어졌을 때

최소 몇 번의 리모컨 버튼 누름으로 그 채널에 갈 수 있는지를 물어보는 문제이다.

리모컨은 M개의 버튼이 고장나 있는데 고장나는 버튼은 숫자 버튼이고

위 아래 버튼은 고장나지 않는다.

처음에는 이 문제를 그리디로 접근해서

1. 100 - N번 채널의 절대 값

2. N - 고장나지 않은 버튼으로 갈 수 있는 N번 채널의 가장 가까운 아래 채널의 절대 값 + 길이

3. N - 고장나지 않은 버튼으로 갈 수 있는 N번 채널의 가장 가까운 위에 채널의 절대 값 + 길이

위 세개 중 최소 값을 구해서 풀려고 했었는데

이 가장 가까운 값을 고르는게 생각보다 싶지 않아

그냥 완전탐색을 이용하여 풀었다.

시간제한은 2초이고 N이 최대 500000이니 O(N)에 충분히 된다.

1. 100 - N번 채널의 절대 값

2. N - 1~10000000까지의 채널 중 고장나지 않는 버튼으로 갈 수 있는 채널의 절대 값 + 길이

위의 두 경우 중 최소 값을 선택하면 된다.

1000000까지 확인하는 이유는 채널은 무제한이고 위로 이동해서 내려오는게 더 가까울 수도 있기 때문이다.

유일한 예외는 채널이 0번 일 때 check함수로는 길이를 못받아오기 때문에 그것에 관한 예외만 해주었다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, cnt;
int arr[11];
 
bool check(int pos){
    if(pos==0) return !arr[pos];
    while(pos){
        if(arr[pos%10]) return false;
        pos/=10;
        cnt++;
    }
    return true;
}
 
int main(){
    scanf("%d %d", &n, &m);
    for(int i=0; i<m; i++){
        int num;
        scanf("%d", &num);
        arr[num] = 1;
    }
 
    int mini = (100 - n);
    if(mini < 0) mini *= -1;
 
    for(int i=0; i<1000000; i++){
        cnt = 0;
        if(check(i)){
            if(i==0) cnt=1;
            int diff = (i - n);
            if(diff < 0) diff *= -1;
            diff+=cnt;
            mini = min(mini, diff);
        }
    }
 
    printf("%d\n", mini);
 
    return 0;
}