[BOJ/백준] 1107 - 리모컨

1107번: 리모컨

---

 

---

---

• 제목

리모컨

---

• 조건

시간 제한 : 2 초

메모리 제한 : 256 MB 

---

• 문제

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

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

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

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

---

• 입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

---

• 출력

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

---

예제 입력1	예제 출력1
5457 3 6 7 8	6

예제 입력2	예제 출력2
100 5 0 1 2 3 4	0

예제 입력3	예제 출력3
500000 8 0 2 3 4 6 7 8 9	11117

예제 입력4	예제 출력4
100 3 1 0 5	0

예제 입력5	예제 출력5
14124 0	5

예제 입력6	예제 출력6
1 9 1 2 3 4 5 6 7 8 9	2

예제 입력7	예제 출력7
80000 2 8 9	2228

---

#include <cmath>
#include <string>
#include <iostream>
using namespace std;
bool button[10];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string tmp;
    int channel, broken, number, min = 500001, cnt, num_down, num_up;
    bool check;
    cin >> channel >> broken;
    
    for(int n = 0 ; n < 10 ; n++){
        button[n] =  true;    
    }
    for(int n = 0 ; n < broken ; n++){
        cin >> number;
        button[number] = false;
    }
    
    // size == 1
    tmp = to_string(channel);
    if(tmp.size() == 1 && button[channel]){
        cout << 1 << endl;
        return 0;
    }
    
    // only use num button
    check = true;
    tmp = to_string(channel);
    for(int n = 0 ; n < tmp.size() ; n++){
        if(button[tmp[n] - '0'] == false)
            check = false;
    }
    if(check){
        cnt = tmp.size();
        if(min > cnt) min = cnt;
    }
    
    // start from 100
    cnt = abs(100 - channel);
    if(min > cnt) min = cnt;
    
    num_up = num_down = channel;
    // start down from number
    while(num_down >= 0){
        check = true;
        num_down--;
        tmp = to_string(num_down);
        for(int n = 0 ; n < tmp.size() ; n++){
            if(button[tmp[n] - '0'] == false)
                check = false;
        }
        cnt = tmp.size() + abs(channel - num_down);
        if(min < cnt) break;
        if(check) break;
    }
    if(min > cnt && num_down >= 0) min = cnt;
    
    // start up from number
    while(true){
        check = true;
        num_up++;
        tmp = to_string(num_up);
        for(int n = 0 ; n < tmp.size() ; n++){
            if(button[tmp[n] - '0'] == false)
                check = false;
        }
        cnt = tmp.size() + abs(channel - num_up);
        if(min < cnt) break;
        if(check) break;
    }
    if(min > cnt) min = cnt;
    
    cout << min << endl;
    return 0;
}