[백준] 리모컨

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

1107번: 리모컨

우선 문제부터 간단하게 요약하면,

100번 채널에서 특정 채널로 리모컨을 이용해서 이동하려 할 때, 

숫자 버튼들이 고장날 수 있습니다. 이 때, 총 몇번의 최소 횟수를 눌러야 이동이 가능한 지를 구해야 하는 문제입니다. (+와 -버튼은 고장나지 않습니다.)

 

<Solution>

우선 두가지 종류의 경우가 있습니다. 

1. 그냥 +와 -버튼으로 100번채널에서 원하는 채널으로 이동하는 방식과,

2. 채널을 특정채널로 이동한 다음 +와 -버튼을 이용해서 원하는 채널로 이동하는 방식

 

이 두가지 경우를 구하면 됩니다. 

 

어떤 방식을 사용해야 하는지 생각해보면, 채널이 0~500,000까지가 가능하므로 리모컨의 조작횟수는 많아봤자 dfs의 깊이 6~(다음 에서 return 시)7정도 까지만 내려갈 것을 예상할 수 있습니다. 더군다나 매 dfs마다 가지의 개수는 대략 10개정도 일 것이므로 깊어봤자 1000만을 넘지 않을 것이므로 bruteforce하면 됩니다. 

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <cmath>

using namespace std;

int toMove, M;
bool button[10+2];
int minCnt = 987654321;

int abs(int a){
    return (a>0) ? a : -a;
}

bool available(){
    for(int i = 0; i<=9; i++){
        if(button[i]) return true;
    }
    return false;
}

void findCnt(int step, int curNum){ // dfs
    if(step == 7){
        return;
    }
    if(step != 0) minCnt = min(minCnt, step + abs(curNum-toMove));
    for(int i = 0; i<=9; i++){
        if(!button[i]) continue;
        curNum += i * pow(10, step); 
        findCnt(step+1, curNum);
        curNum -= i * pow(10, step);
    }
}

int main(){
    cin >> toMove >> M;
    
    for(int i = 0; i<10; i++){
        button[i] = true;
    }
    for (int i = 0; i<M; i++){
        int k;
        cin >> k; 
        button[k] = false;
    }

    // just move using ++ --
    minCnt = min(minCnt, abs(100-toMove));

    // move and use ++ --
    // move to closest one
    // if all buttons are not available, skip
    if(available()){
        findCnt(0, 0);
    }

    cout << minCnt << endl;

    return 0;

}