[알고리즘] 백준 1107 리모컨

1107 리모컨

문제의 조건

1. 초기 채널은 100이다.
2. 고장난 버튼이 존재한다.

문제의 조건에 따라 ret 변수를 |n-100| 으로 설정하고 진행하였다.
고장난 버튼을 brok 배열을 통해 사용하였고 고장난 버튼 설정을 먼저 한다.
+- 버튼을 통해 이동하기 전, 리모컨의 숫자 버튼으로 입력되는 값을 기준으로 0부터 1000000(1000000에서 500000으로 내려오는 경우도 생각)까지 for문을 돌려가며 각 값을 모두 check한다.

check함수는 해당 값을 리모컨으로 만들 수 있으면 값의 자릿수를, 아니면 -1을 리턴한다.

check가 -1이 아니면 |i-n| + nt (리모컨을 누르는 횟수) 와 ret 중 작은 값을 ret로 만든다.

풀이

#include <bits/stdc++.h>
using namespace std;
int n,m,ret,brok[10];

int check(int ch){
    if(ch == 0){
        if(brok[0]) return -1;
        else return 1;
    }
    int ret = 0;
    while(ch){
        int tmp = ch % 10;
        ch /= 10;
        if(brok[tmp]) return -1;
        ret++;
    }
    
    return ret;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<m;i++) {
        int a; cin>>a;
        brok[a] = 1;
    }
    ret = abs(n - 100);
    for(int i=0;i<1000000;i++){
        int nt = check(i);
        if(nt >= 0){
            ret = min(ret, abs(i - n) + nt);
        }
    }
    cout<<ret;
}