[1107] 리모컨(C++)

문제

바로가기

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

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

채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

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

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

 

 

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.

둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다.

고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

 

 

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

 

 

해결 방법

브루트포스로 접근해야 된다는 것은 알았지만 무작정 모든 번호가 가능한지, 불가능한지 탐색하는 것보다 목표하는 채널을 기준으로 코드를 짜면 좀 더 효율적이지 않을까 하다가 너무 복잡해지는 것 같아서 포기

 

브루트포스 문제는 모든 경우를 탐색해도 어차피 시간 초과가 나지 않기 때문에 뭘 어떻게 더 효율적으로 할까 고민하는 것보다 그냥 최소 범위부터 최대 범위까지 냅다 돌리는 게 나을 것 같다.

 

이 문제는 크게 3가지를 비교해봐야 한다.

1. + 버튼만 계속 누르는 경우
2. - 버튼만 계속 누르는 경우
3. 특정 채널로 이동한 후, + 또는 - 버튼을 누르는 경우

1, 2번은 쉽지만 3번은 주의해야 될 것이 있다.

최대 몇 번 채널까지 탐색해야 되느냐인데, 목표 채널이 최대 500000번까지 있을 수 있고 만약 현재 사용 가능한 번호가 0과 1 뿐이라면 3번의 경우에서 내가 이동할 수 있는 채널은 1000000이다. 따라서 탐색 범위가 N의 최댓값인 500000이 아니라 1000000인 것이다.

 

 

내 코드(C++)

// [1107] 리모컨
// 브루트포스
#include <iostream>
#include <string>
#include <cstdlib> // abs
#define MAX 1000000 // N = 500000번이고 2~9번이 모두 고장난 경우 1, 0으로 채널을 만들어야됨 -> 최대 1000000
using namespace std;

int n; 
bool state[10]; 

void input()
{
    int m, tmp;
    cin >> n >> m;
    for(int i = 0 ; i < 10 ; i++) state[i] = true; // init
    for(int i = 0 ; i < m ; i++) {
        cin >> tmp;
        state[tmp] = false;
    }
}

bool check(int num) {
    if(num == 0) {
        if(state[0] == false) return false;
        else return true;
    }
    while(num) {
        if(state[num % 10] == false) return false;
        num /= 10;
    }
    return true;
}

int getMin(int num)
{   
    int minPressCnt = MAX, pressCnt;
    for(int i = 0; i <= MAX ; i++) {
        if(check(i)) { // 고장난 번호 없이 누를 수 있는 경우
            pressCnt = to_string(i).length();
            pressCnt += abs(i - num);
            minPressCnt = min(minPressCnt, pressCnt);
        }
    }
    // 100번에서 + or - 로 계속 이동하는 것과 비교
    return min(abs(num - 100), minPressCnt);
}   

int main(void)
{
    input();
    cout << getMin(n) << '\n';
    return 0;
}