[ 백준 1107 ] 리모컨 (c/c++)

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

 

 

[ 문제 요약 ]

100번에서 리모콘을 이용해서 N번 채널로 옮기려고 한다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않는다. 또한 M개의 고장난 버튼이 주어질 때 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지 출력한다.

 

 

[ 문제 풀이 ]

1. 우선 100번에서 N까지 +, - 만을 이용해서 이동하는 횟수를 구한다.

2. 0번부터 1000000번 까지 모든 채널에 대해서 고장난 버튼의 번호가 있는지 없는지 확인한다.

3. 만약 고장난 버튼의 번호가 있다면 누를 수 없는 채널이기 때문에 넘어간다.

4. 누를 수 있다면 절대값과 채널 번호의 길이를 더해 버튼을 눌러야 하는 횟수를 구해 최솟값을 구한다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int N, M, ans, cnt;
int arr[11];

int Find(int n) {
    if (n == 0){
        if (arr[0]) return 0;
        return 1;
    }
    while(n) {
        if (arr[n % 10]) return 0;
        n = n / 10;
    }
    return 1;
}

int main() {
    cin >> N >> M;
    for (int i=0; i<M; i++) {
        int a;
        cin >> a;
        arr[a] = 1;
    }

    ans = abs(N - 100);

    for (int i=0; i<=10000000; i++){
        if (Find(i)){
            cnt = to_string(i).length();
            cnt = cnt + abs(i - N);
            ans = min(cnt, ans);
        }
    }

    cout << ans;
    
    return 0;
}

 

 

 

[ 주의할 점 ]

500000번까지만 확인할 경우 511111번과 같이 그 이후의 채널에서 하는 것이 더욱 유리할 경우를 계산할 수 없기 때문에 그 두배인 10000000번까지의 채널을 확인해야 한다.