BOJ/1107 리모컨

https://noj.am/1107

solved.ac class3에 있는 문제여서 풀게 되었다.
예전에도 한 번 시도하다 포기한 기억이 있었던 문제라 마음먹고 풀었는데 생각보다 까다로웠다.

처음에 가능한 경우의 수를 나눠서 접근했다.
1. 바로 이동하려는 채널로 눌러서 이동이 가능한 경우
2. 최대한 가까운 채널로 이동한 후 +, -를 사용해서 목표 채널로 이동하는 경우
3. +, -버튼만 이용해서 목표 채널로 이동하는 경우

세 가지 경우를 나눠서 생각하고 구현해보니 2번의 경우 최대한 가까운 채널을 찾는 과정이 더 큰 채널로 이동할 지 작은 채널로 이동할 지 나누는 과정이 복잡해졌다.
구현하자면 할 순 있을 거 같았지만 다시 생각을 해보기로 했고 0 <= N <= 500,000 인 조건을 보고 최대한 가까운 채널을 찾기 보단 0 ~ 1,000,000까지 모두 돌아보면서(브루트포스) 해결해도 시간이 충분할 것으로 생각되었다.

실제 코드에선 1과 2를 한 번에 처리하고 3을 따로 처리했다

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m;
bool isBroke[10]; // 고장난 버튼 체크
int now = 100;

int solve() {
    int ret = INT_MAX;

    for (int i = 0; i <= 1000000; ++i) { // 모든 경우의 수
        int k = i, subret = 0;
        bool success = true;

        while (k) { // i != 0 인 경우
            if (isBroke[k % 10]) {
                success = false;
                break;
            }
            subret++;
            k /= 10;
        }
        if (i == 0) { // i == 0 인 경우 예외처리
            if (isBroke[0]) success = false;
            else subret = 1;
        }


        // +, - 버튼만 이용하는 경우
        subret += abs(n - i);

        if (success)
            ret = min(ret, subret);
    }


    ret = min(ret, abs(n - 100));
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int tmp;
        cin >> tmp;
        isBroke[tmp] = true;
    }

    cout << solve() << '\n';
}