백준 1107 - 리모컨

C++

1107 번 - 리모컨

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다. 문제 출처

접근 방법

처음에 이동하려는 채널 N의 각 자리의 숫자에 최대한 가까운 번호를 입력하여 그 차이를 통해 문제의 답을 구하려 하였지만, 반례가 많았으며 특히 주어진 채널 보다 높은 번호를 입력해 내려가는 경우에서 문제가 봉착하였다.

따라서 시간초과에 구애받지 않고, 완전 탐색으로 0에서 부터 모든 번호를 하나씩 확인하여 가장 최소 입력으로 주어진 채널에 도달 할 수 있는 번호를 찾는 방식으로 해결하였다.

구현

고장난 리모컨 버튼을 나타내는 방법은, 0 부터 9까지 총 10개의 숫자가 들어있는 배열을 나타내며, 각 숫자의 위치 즉 인덱스는 해당하는 숫자와 같으므로, 고장난 버튼을 주어지면 해당 숫자는 -1로 두어 고장난 버튼이라고 표기한다.

총 3가지의 경우를 생각하였다.

1. 모든 버튼이 고장났을 경우
2. 상 하 버튼으로만 이동하는 경우
3. 숫자 버튼을 입력하되, 이 숫자가 리모콘으로 입력이 가능하다면 그 번호에서 상 하 버튼으로 이동하는 경우

첫번째 경우

먼저 첫번째 경우에는 리모콘에 입력 할 수 있는 숫자가 없으므로, 상 하 버튼으로만 이동한다. 따라서 N에서 100을 뺀 값이 총 클릭한 수이며, N이 100보다 작은 경우를 대비하여 절대값 abs로 양수로 출력하고 종료한다.

두번째 경우

주어진 번호가 예시와 같이 100이거나 [98, 99, 101, 102]와 같이 굳이 숫자를 입력하지 않아도 상/하 버튼으로만 이동하는게 제일 빠를 경우이다. 이는 첫번째 경우와 똑같이 구할 수 있으며, 세번째 경우와 비교하여 세번째보다 더 적은 횟수로 이동한다면, 이 값을 답으로 출력한다.

세번째 경우

숫자를 입력하고, 리모콘에 고장난 숫자가 있어 바로 도달하지 못한다면, 상/하 버튼으로 도달하는 경우이다.
제일 최소의 클릭 횟수로 주어진 채널에 도달하는 입력 번호의 값을 찾기 위해 0부터 888888까지의 번호들을 탐색한다.
마지막 번호의 기준이 888888인 이유는 만약,

499999  
8  
0 1 2 3 4 5 6 7  

라는 테스트 케이스가 주어지면, 리모콘에 누를 수 있는 번호가 8과 9밖에 없으므로 8을 6개 입력하여 내려가는 경우가 번호를 입력하여 이동하는 경우에서 제일 큰 결과이기 때문이다.
만약 8이 아니라 9인 경우에는 100에서 올라가는것이 999999에서 내려가는 경우에서 보다 횟수가 적으므로, 기준이 8이 되는것이다.

이후 각 반복되는 숫자들을 string으로 변환하고, 각 자리의 숫자를 처음 리모콘이라고 구현한 배열의 인덱스에 대입하여 그 위치의 값이 -1이 아니라면 입력한 번호와 주어진 번호의 차이(상/하 버튼으로 도달) + 번호를 입력하기 위해 버튼을 누른 횟수를 기존의 result와 비교하여 최소 값을 저장한다.

이후 반복하여 최소 횟수를 구한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <math.h>

using namespace std;

int result = 999999;
int n, k;
int arr[10] = { 0,1,2,3,4,5,6,7,8,9 };
bool chkBtn(string num);

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

    cin >> n >> k;

    //리모컨 만들기
    int eraseNum;
    for (int i = 0; i < k; i++) {
        cin >> eraseNum;
        arr[eraseNum] = -1;
    }

    //모든 리모콘 버튼이 고장 났을 시
    if (k == 10){
        cout << abs(n - 100);    // 상/하 버튼만으로 해당하는 채널로 간다.
        return 0;
    }

    //버튼을 0부터 888888까지 눌러보며 탐색한다.
    for (int i = 0; i <= 888888; i++) {
        string str = to_string(i);
        if (!chkBtn(str)) {     //해당하는 숫자가 리모콘으로 입력 할 수 없으면, 다음 번호로 넘어간다.
            continue;
        }
        int diff = abs(n - i) + str.size(); //입력한 번호와 주어진 번호의 차이(상/하 버튼으로 도달) + 번호를 입력하기 위해 버튼을 누른 횟수 
        result = min(result, diff);
    }

    // 상/하 버튼으로만 이동한 총 클릭수와 비교
    result = min(result, abs(n - 100));

    cout << result << "\n";
}

//주어진 번호가 리모콘으로 누를 수 있는 번호인지 확인
bool chkBtn(string num) {
    
    for (int i = 0; i < num.size(); i++) {
        if (arr[num[i] - '0'] == -1)        //고장난 버튼은 -1이며, 주어진 각 자리의 숫자가 리모콘의 버튼을 나타내는 배열의 인덱스와 일치하므로 확인
            return false;
    }
    return true;
}

후기 및 개선할 점

총 테스트 케이스의 개수는 888888개 이며, 총 시간복잡도는 O(n^2)이다.
이 시간 복잡도가 주어진 문제의 시간 제한에 걸리지 않을 꺼라는 판단은 어디서 알 수 있는지 궁금하다.
이 문제의 시간 제한은 2초인데, 내가 이 문제를 해결하며 clock_t로 시간을 재면 최대 12초 까지 나온다. 따라서 백준에서 채점 할 때, 시간이랑 내가 문제를 풀 때 걸리는 시간이랑 다르다는 건데,,, 이 기준을 몰라 고민을 한 문제였다.