[백준 1107][브루트포스][C++] 리모컨

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

1107번: 리모컨

깊게 생각해서 오히려 더 헤맸던 문제였다. 브루트포스로 접근하니 금방 풀린 문제이다.

 

처음 시작하는 채널은 100번. 리모컨의 부서진 버튼은 배열에 따로 체크해둔다.

 

그리고, 이 문제에서 가능한 모든 채널을 0번부터 탐색해준다. 약 100만 채널까지 탐색하면 되겠다.

 

그 채널을 가기 위해 필요한 버튼을 누르는 횟수(0번은 불가능을 뜻한다)를 반환하는 함수로 매 채널마다 리모컨의 숫자 버튼을 눌러 갈 수 있는지, 갈 수 있다면 그 채널로부터 몇 번 +-버튼을 눌러서 갈 수 있는지, 버튼을 누르는 횟수를 합하여 최솟값을 구해서 출력해준다.

#include<iostream>
#include<cmath>
#include<cstdlib>
using namespace std;
int broke[10]={};

int avail(int n){
    if(n==0) return broke[0]==0 ? 1 : 0; // n이 한자리지만 0이므로 따로 처리해준다
    int count=0;
    while(n>0){ // n의 자릿수만큼 버튼을 누르는 횟수가 증가한다.
        if(broke[n%10]==1){ // 버튼이 부서져있으면 채널 이동 불가능
            return 0;
        }
        count++;
        n/=10;
    }
    return count;
}

int main(){
    int s, m, input, count; // s는 가려하는 채널, m은 부서진 버튼의 개수
    cin>>s>>m;
    for(int i=0; i<m; i++){
        cin>>input; broke[input]++; // 부서진 버튼을 체크해둔다
    }
    int channel=100, ans=abs(s-channel); //ans에 +-만 사용했을 때 필요한 횟수
    
    for(int i=0; i<=1000000; i++){
        if(avail(i)){
            count = abs(s-i)+avail(i); //횟수가 음수가 되면 안되므로 절댓값을 취해준다
            if(ans>count){
                ans=count;
            }
        }
    }
    cout<<ans;
}