[백준 1107] 리모컨

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

최솟값의 초기값은 초기 채널에서 +,-만 눌러서 목표채널로 이동하는 횟수. 이 값보다 버튼 클릭 횟수가 커지면 최솟값이 될 수 없다.

채널을 0부터 시작해서 1씩 증가시키며 현재 채널이 리모컨으로 입력 가능한지 확인한다.

입력 가능하면 목표채널까지 몇번만에 갈 수 있는지 확인.

이때 리모컨 입력 횟수는 "현재 채널을 입력하고 +,-만 입력하여 목표채널로 간 횟수"

이 값이 최솟값보다 작으면 최솟값을 업데이트 해준다.

현재 채널을 입력하는 횟수는 채널의 자릿수 길이고 +,-만 입력하여 목표채널로 가는 횟수는 현재채널과 목표채널의 차이값이다.

채널 탐색 범위가 500,000을 초과하는 이유

예를 들어 목표채널이 500,000인데 6 버튼 만 입력 가능할 경우 최소 클릭 횟수는 666,666 채널을 입력한 후 -버튼을 166,666번 누르는 것이기 때문에 500,000 보다 높은 채널의 경우도 고려해야한다.  

C++ code

#include <iostream>
#include <vector>
using namespace std;
bool check(vector<bool>& avail, int n){
    if(n == 0 && avail[n] == false)
        return false;
    while(n){
        if(avail[n%10] == false)
            return false;
        n /= 10;
    }
    return true;    
}
int distance(int a, int b){
    return a > b ? a-b : b-a;
}
int length(int a){
    int len = 0;
    do{
        len++;
        a /= 10;
    }while(a);
    return len;
}
int main(){
    int n;
    cin >> n;
    int m;
    cin >> m;
    vector<bool> avail(10,true);
    int temp;
    for(int i = 0; i < m; i++){
        cin >> temp;
        avail[temp] = false;
    }
    int min = distance(n,100);
    for(int i = 0; i < 1000000; i++){
        if(check(avail,i)){
            temp = distance(n,i) + length(i);
            min = min < temp ? min : temp;
        }     
    }
    cout << min;
    return 0;
}