[cpp]백준 1107번 리모컨

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

1107번: 리모컨

 이 문제를 본 건 엄청 오래됐다. 3년 전에도 봤었고, 그 뒤로도 몇 번 풀이를 생각했으나 못 풀었던 문제다. 요즘엔 알고리즘을 나름 꾸준히 풀고 있어서 무슨 수를 써서든 풀 수 있을 거란 확신이 있었다. 처음엔 1ms 도 아니고 1μs 안에 돌아가는 알고리즘을 생각했지만, 구현이 매우 어렵고 예외처리도 많이 해야 한다. 그 뒤에 아주 간단한 풀이 방법이 생각 났는데, 왜 이걸 이제 생각했는지 모르겠다.

 풀이 : min (0~1000000 까지 각각 숫자를 입력한 뒤 이동하는 횟수 + 입력한 숫자의 개수), (100번 채널에서 떨어진 거리)

 처음 보고 있는 채널이 100번이기 때문에 사실 1000000-100-6 까지만 확인해도 될 것이다.

 getCount 함수는 해당 채널로 이동하려면 몇 번 이동해야하는지 반환해 준다. 만약 불가능하다면 매우 큰 숫자를 반환한다.

 예외 : getCount 내에 있는 while 문은 n > 0 일때 작동하기 때문에 n == 0 일 경우에 유의하자!

#include <iostream>
#include <cstdio>
#include <utility>
#include <algorithm>
#include <cmath>

using namespace std;

int target;
bool error[10];

int getCount(int n) {
    int cnt = 0;

    if (n == 0) {
        if(error[0]) return 1000000;
        return 1;
    }

    while (n) {
        ++cnt;
        int component = n % 10;
        if (error[component]) return 1000000;
        n /= 10;
    }
    
    return cnt;
}

int main() {
    int n;

    cin >> target;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int input;
        scanf("%d", &input);
        error[input] = true;
    }

    int result = abs(target - 100);
    for (int i = 0; i < 1000000; ++i) {
        int cnt = getCount(i);
        result = min(result, cnt + abs(target - i));
    }
    cout << result << endl;

    return 0;
}