백준 1107 - 리모컨

문제

 

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

1107번: 리모컨

 

 

풀이

 

0부터 백만까지 이동 가능한 모든 채널을 선택하고, 선택한 채널에서 N번으로 이동했을 때의 값들 중 최소를 구하면 된다. 백만까지 반복하는 이유는, 예를 들어 N=500000이고 사용할 수 있는 버튼이 6만 있을 경우 666666으로 이동한 후 50만까지 -를 누르면 된다. 이처럼 이동하고 싶은 채널 N은 50만이 최대지만 실제로 이동할 수 있는 채널은 N*2까지 가능하다. 

그리고 현재 채널이 100번이므로 이 채널에서 +나 -로만 이동해서 N까지 이동하는 경우도 생각해야 한다. 

 

 

코드

 

#include <iostream>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
int N, M;
bool broken[10];
 
int check(int a)
{
    if (a == 0) return (broken[a] ? 0 : 1);
 
    int len = 0;
    while(a)
    {
         if (broken[a % 10]) return 0;
         a /= 10;
         len++;
    }
    return len;
}
 
int main()
{
    cin >> N >> M;
 
    int num;
    while (M--)
    {
        cin >> num;
        broken[num] = true;
    }
 
    int result = abs(N - 100);
 
    int len;
    for (int i=0; i<=1000000; i++)
    {
        len = check(i);
        if (!len) continue;
        result = min(result, abs(N - i) + len);
    }
 
    cout << result;
 
    return 0;
}