[백준] 1107번 리모컨

문제

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

풀이과정

리모컨이 부숴졌으면 고치면 되지 왜 그러는지 참 아무튼 리모컨의 어떤 숫자 버튼이 고장났을 경우 +,- 버튼을 통해 이동하고 싶은 채널로 가야한다.
이 때, 최소 이동횟수를 구하는 문제다. 브루트 포스를 이용하면 풀 수 있었다.

처음 초기값은 문제에서 지금 보고있는 채널이 100번이므로 abs(N-100) 으로 지정한다.

그리고 0번부터 100만까지 채널을 하나하나 탐색해서 제일 짧은 이동횟수를 구한다. (100만인 이유는 범위는 50만까지지만 채널 이동은 50만 위로 올라가서 -버튼을 누르는 경우가 있기 때문)

소스코드를 보면 이해하기가 더욱 쉽다.

소스코드

#include <iostream>

using namespace std;

#define MAX_M 1000000

// 고장난 버튼을 체크
bool chk[10];

// c라는 숫자를 버튼으로 눌러 이동할 경우 이동할 수 있다면 숫자버튼을 누르는 횟수를 리턴
int possible(int c)
{
    // 0인 경우 처리
    if (c == 0)
    {
        return chk[0] ? 0 : 1;
    }

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

    return len;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N,M;

    cin >> N;

    cin >> M;

    // 고장난 버튼 처리
    while (M--)
    {
        int broken_btn;
        cin >> broken_btn;
        chk[broken_btn] = true;
    }

    int ans = abs(N - 100);

    // 완전탐색 과정 1부터 차례대로 검사해서 
    for (int i = 0; i < MAX_M; i++)
    {
        int c = i;
        // 숫자버튼이 고장나지 않아서 그 채널로 이동할 수 있다면 (숫자버튼을 누르는 횟수 + 이동하려는 채널과의 차이)
        int cmp_ans=possible(c) ? possible(c)+abs(N-c):abs(N-100);

        if (ans > cmp_ans)
            ans = cmp_ans;
    }

    cout << ans << "\n";

    return 0;
}