[백준 1107] 리모컨

작성일 | In |

문제 링크

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

풀이

현재 채널인 $100$번에서 +, - 버튼으로만 $N$번 채널까지 이동한다면 $abs(N-100)$번 버튼을 눌러야 합니다. 이를 +, - 버튼을 누르는 횟수의 상한으로 잡는다면 숫자를 통해 이동할 수 있는 채널의 범위를 찾아낼 수 있고 $[N-abs(N-100), N+abs(N+100)]$, 이 범위의 길이는 최대 $2N$이므로 충분히 범위안의 채널을 모두 탐색해도 시간내에 돌 수 있습니다. 누르는 숫자 버튼의 개수와 +, -버튼을 통해 이동하는 횟수를 모두 구해 그 중 최솟값을 정답으로 출력하면 됩니다. 누를 수 없는 채널과 0번 채널로 이동하는 경우를 유의하며 구현해야 합니다. 시간복잡도는 탐색하는 채널의 개수인 $O(N)$입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m, chk[10], INF = 1e9;

int f(int x){
    if(x < 0) return INF;
    if(x == 0) return chk[0] ? INF : 1;
    int c = 0;
    while(x){
        if(chk[x % 10]) return INF;
        x /= 10, c++;
    }
    return c;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int a; cin >> a;
        chk[a] = 1;
    }

    int k = abs(n - 100);

    int mn = k;
    for(int i=n-k;i<=n+k;i++) mn = min(mn, f(i) + abs(i - n));
    cout << mn;
}