[boj] 백준 1107 리모컨 - 브루트포스

[문제]

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

1107번: 리모컨

 

[풀이]

범위가 크지 않아 브루트포스 완전 탐색 방식으로 해결할 수 있다.

이동하고자 하는 채널은 0<=channel<=500,000 이지만 위에서 -를 눌러 내려오는 경우도 생각을 해야하므로 0에서 1000000까지 채널을 고려해준다. 100번 채널에서 시작을 하기 때문에 abs(n-100)을 처음 답으로 두었다. 모든 채널에 대해서 고장난 버튼이 없을 때, 그 채널로 가기 위해 누르는 버튼의 수와(채널의 길이) 목표 채널인 n으로 가기 위해 누르는 +- 버튼 수를 더해 최종 횟수를 구해주고, 이를 최소값으로 계속 갱신해준다. 

 

[코드]

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace::std;

bool broken[10];

bool possible(string sn){
    for(int i=0; i<sn.length(); i++){
        int num = sn[i]-'0';
        if(broken[num]){
            return false;
        }
    }
    return true;
}

int solve(int n){
    int answer = abs(n-100);
    for(int i=0; i<=1000000; i++){
        string sn = to_string(i);
        if(possible(sn)){
            //버튼을 누른 횟수
            int cnt = sn.length();
            cnt += abs(n-i);
            answer = min(cnt, answer); //최소로 버튼을 누른 횟수 갱신
        }
    }

    return answer;

}

int main() {
    //100번에서 채널 n으로 이동하기 위해서는 버튼을 최소 몇 번 눌러야 하는지.
    //이동하려는 채널 n, 고장난 버튼의 개수 m
    int n, m, a;
    cin >> n >> m;
    for(int i=0; i<m; i++){
        cin >> a;
        broken[a] = true; //고장난 버튼
    }

    if(n==100)
        cout << "0";
    else
        cout << solve(n);

}