[BOJ] 1107 리모컨

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

1107번: 리모컨

문제

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

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

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

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

입력

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

출력

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

---

풀이

브루트포스문제를 풀 때는 구현 문제라고 생각하면서 풀면 안되는 것을 다시 생각해주는 문제였다.

구현처럼 풀었다가 너무 많은 반례들이 존재하여 결국 다른 분의 코드를 참조하였다.

 

1. 먼저 가고 싶은 채널을 100에서 +나 -만을 눌러가는 경우의 값을 답으로 저장한다.
2. 0번 채널부터 1,000,000번 채널까지 모든 채널을 돌면서 채널을 입력할 수 있는지 확인한다.
3. 채널을 입력할 수 있다면 해당 채널에서 원하는 채널까지 가는데 누른 버튼 횟수를 답과 비교하여 최소일 경우 답으로 저장한다.

조심해야 할 점은 채널을 입력할 수 있는지 확인 할 때 만약 0번 채널을 확인 할 경우 예외 처리를 해줘야 한다는 것이다.

---

코드

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>

#define SWAP(a, b, type) do { \
    type temp; \
    temp = a;  \
    a = b;     \
    b = temp;  \
} while (0)

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int N,M;

bool broken[10];

int check(int n) {
    if(n==0&&!broken[0]) return 1; //0번 채널 예외처리
    
    int cnt=0;
    while (n > 0) {
        if (broken[n % 10]) return 0;
        n = n / 10;
        cnt++;
    }
    return cnt;
}

void input() {
    cin>>N>>M;
    int x;
    for(int i=0;i<M;i++){
        cin>>x;
        broken[x]=true;
    }
}

void init() {
    
}


void solution() {
    int result = abs(N-100);        // +나 -를 눌러서 답이나오는 경우를 result로 잡는다.
    
    for (int i = 0; i <= 1000000; i++) {
        int cnt = check(i);         //해당번호를 누를 수 있는지 확인한다.
        if (cnt > 0) {
            int press = abs(i - N); //해당번호를 누를 수 있다면 그 번호에서 얼마나 +를
                                    //눌러야 N에 도달할 수 있는지를 구한다.
            result=min(result,press+cnt);
        }
    }
    cout<<result;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}