BOJ 1107 - 리모컨

전부터 풀어야지 생각하고 어떤 알고리즘으로 풀지까지 다 생각을 해뒀던 문제인데 미루고 미루다가 드디어 풀게 되었다.

발상은 간단하다.
정말 0번 채널부터 해서 모든 채널을 일일히 확인해보는 것이다. 채널 번호를 하나 줄인 뒤, 그 번호에 고장난 버튼의 숫자가 들어있는지 확인, 들어있지 않다면 버튼을 누르는 횟수를 계산, 이 것을 채널 번호가 0이 될 때까지 반복한다. 반대로, 채널 번호를 위로 올린 뒤, 확인하고, 100만이 될 때까지 반복하면 위의 범위까지 모두 검사한 것이 된다.

여기서 100만까지 검사를 하는 이유는, N의 범위가 50만까지이기 때문이다. 채널 번호가 50만일 경우, 그보다 작은 채널 번호 중에서 가장 차이가 많이 나는 것은 0번 채널이다. 이 때의 차이는 50만이다. 따라서 그만큼 차이가 나는 100만번 채널까지 검사를 해 주는 것이다. 그 이상이 되면 무슨 값이든 0일 때보다는 버튼을 누르는 횟수가 많아져서, 절대 정답이 될 수가 없다.

이걸 일일히 검사해도 될 것이라고 판단하게 된 것은 애초에 검사해야하는 채널의 범위가 0부터 100만으로 굉장히 작기 때문이다. 이 문제의 제한시간은 2초이고, c++ 기준 2초면 2억 개의 계산을 할 수 있기 때문에 한 채널을 검사할 때 2억 / 100만 = 200개의 연산을 할 수가 있는데, 딱 생각해봐도 그 정도 연산은 한 채널 검사에 필요하지 않는다. 따라서 시간은 널널하다고 바로 판단이 가능하다.
시간 복잡도를 생각해보면, 언제나 100만 번 연산을 수행한다고 생각하면 될 것 같다. 채널 수에 비례해서 연산 수가 변화하는 게 아니라 언제나 고정이라 뭐라고 표기를 해야 할 지 애매하다...

for (int i = 0; i < l; i++) {
       if (broken.find(s[i] - '0') != broken.end()) continue;
}
cnt = min(abs(t - n) + l, cnt);

맨 처음에 코드를 짤 때 이렇게 썼는데, 내가 원하는 결과는 만약 고장난 버튼을 저장한 set broken에서 s[i]를 찾으면 break하고 다음 루프롤 돌아가는 것이었지만, s[i]을 찾아도 계속 find를 해서 당황했었다.
근데... 그게 당연하다... 무슨 break도 아니고 continue를 걸었으니 당연히 무시하고 다음 루프를 돌겠지...
그리고 여기서 continue를 걸어야 되는 루프는 이 루프가 아니라 얘를 감싸고 있는 채널 번호를 줄이거나 늘리는 루프이다. 따라서 저 부분은 만약 s[i]를 찾았을 시 flag를 true로 해준 뒤 break한 뒤, flag가 true일 경우 for을 감싼 루프를 continue해서 cnt를 계산하지 않도록 해주었다.

참고로 여기서 고장난 버튼이 채널 번호에 포함되어 있을 때 cnt를 계산해주지 않는 이유는, 그 채널에 접근하는 것이 불가능하기 때문이다. (당연)

//리모컨 - 골드 5

#include <iostream>
#include <set>
#include <cmath>
#include <string>

using namespace std;

#define MAX_CH 500000

int main() {
    int n, m, t, cnt = 0;
    char temp;
    bool flag = false;
    set<int> broken;
    cin >> n >> m;

    cnt = abs(100-n);

    if (!m) {
        int l = to_string(n).length();
        cout << min(l, cnt);
        return 0;
    }
    for (int i = 0; i < m; i++) {
        cin >> t;
        broken.insert(t);
    }



    t = n;
    while (t > 0) {
        t--;
        string s = to_string(t);
        int l = s.length();
        for (int i = 0; i < l; i++) {
            if (broken.find(s[i] - '0') != broken.end()) {
                flag = true;
                break;
            }
        }
        if (flag) {
            flag = false;
            continue;
        }
        cnt = min(abs(t - n) + l, cnt);
    }

    t = n;
    while (t < MAX_CH * 2) {
        t++;
        string s = to_string(t);
        int l = s.length();
        for (int i = 0; i < l; i++) {
            if (broken.find(s[i] - '0') != broken.end()) {
                flag = true;
                break;
            }
        }
        if (flag) {
            flag = false;
            continue;
        }
        cnt = min(abs(t - n) + l, cnt);
    }
    cout << cnt;
}

그렇게 해서 이렇게 제출을 했는데... 틀렸다!

이유는 간단했다. 나는 채널 번호가 n이면 0~n-1, n+1~MAX_CH까지만 검사를 했지, 정작 n일 때 검사를 하지를 않았다. 근데 n일 때도 cnt가 최소가 되는 것이 가능하다. 뭐 채널 번호가 1234인데 고장난 버튼은 0567 이러면 그냥 1234 누르는 게 최소니까...

이런 멍청한 실수를 했다는 사실을 깨닫고 바로 수정했다. 숫자를 늘리는 루프 앞에서 t를 n-1로 해주었다. 이러면 루프에 들어갔을 때 t가 n이 되니까 n일 때도 검사를 하게 된다.

---

결과적으로 정답을 얻은 코드는 다음과 같다.

//리모컨 - 골드 5

#include <iostream>
#include <set>
#include <cmath>
#include <string>

using namespace std;

#define MAX_CH 500000

int main() {
    int n, m, t, cnt = 0;
    char temp;
    bool flag = false;
    set<int> broken;
    cin >> n >> m;

    cnt = abs(100-n);

    if (!m) {
        int l = to_string(n).length();
        cout << min(l, cnt);
        return 0;
    }
    for (int i = 0; i < m; i++) {
        cin >> t;
        broken.insert(t);
    }



    t = n;
    while (t > 0) {
        t--;
        string s = to_string(t);
        int l = s.length();
        for (int i = 0; i < l; i++) {
            if (broken.find(s[i] - '0') != broken.end()) {
                flag = true;
                break;
            }
        }
        if (flag) {
            flag = false;
            continue;
        }
        cnt = min(abs(t - n) + l, cnt);
    }

    t = n-1;
    while (t < MAX_CH * 2) {
        t++;
        string s = to_string(t);
        int l = s.length();
        for (int i = 0; i < l; i++) {
            if (broken.find(s[i] - '0') != broken.end()) {
                flag = true;
                break;
            }
        }
        if (flag) {
            flag = false;
            continue;
        }
        cnt = min(abs(t - n) + l, cnt);
    }
    cout << cnt;
}

계산을 얼추 해보고 브루트포스로도 충분히 풀린다는 점을 캐치하면 간단한 구현으로 풀 수 있는 간단한 문제였다.