[백준 / BOJ / GOLD 5] 1107번 : 리모컨

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

1107번: 리모컨

 

원하는 채널로 이동하기 위한 최소 버튼을 구하는 문제입니다.

최초 채널이 100이라는 점을 잊지 말아야 합니다.

항상 같은 자리수가 최단 거리가 아닐 수 있다는 것도 가정해야합니다.

• 이동하고 싶은 채널 999
• 고장난 버튼 수 7개
• 고장난 버튼 2,3,4,5,6,7,9

이런 경우 888에서 999로 이동하는 것 보다 1000에서 999로 이동하는게 버튼을 누르는 횟수가 적습니다.

 

아래는 작성한 코드입니다.

#include <iostream>
 
using namespace std;
 
bool brokenButton[10];
 
int possible(int num)                        // 누를수 있는 버튼인지를 체크
{
    if (num == 0)
    {
        if (brokenButton[0])
        {
            return 0;
        }
        else
        {
            return 1;
        }
    }
 
    int length = 0;
 
    while (num)
    {
        if (brokenButton[num % 10])
        {
            return 0;
        }
        length++;
        num /= 10;
    }
 
    return length;                            // 입력된 채널의 길이를 리턴
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int a, b;
    cin >> a >> b;
 
    for (int i = 0; i < b; i++)
    {
        int c;
        cin >> c;
        brokenButton[c] = true;
    }
 
    int ans = a - 100;                        // 초기값
    if (ans < 0)
    {
        ans = -ans;
    }
 
    for (int i = 0; i <= 1000000; i++)
    {
        int length = possible(i);
 
        if (length > 0)
        {
            int click = i - a;                // +,-를 누르는 횟수
            if (click < 0)
            {
                click = -click;
            }
 
            if (ans > length + click)
            {
                ans = length + click;
            }
        }
    }
 
    cout << ans << "\n";
 
    return 0;
 
}