[C++/BOJ] 1107 : 리모컨 (완전탐색)

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

 

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

---

백준 골드 5 문제.

 

처음에는 가장 가까운 수부터 반복문을 돌리면서, 고장난 버튼을 포함하지 않는 수를 발견하면

반복문을 끝내면 될 것 같았는데

생각해보니 예외도 많을 것 같았고 N보다 작은 쪽으로 가는 경우도 있고 <-> 큰 쪽으로 가는 경우도 있기 때문에

결국 똑같아서 완탐으로 풀었다..

 

주의사항은 범위가 500,000이지만 최대 수가 입력되어도 그것보다 큰 수부터 리모컨 조작을 시작해야할 수도 있으므로

범위를 1,000,000까지 찾아주는게 중요하다

 

Xucking Brute Force!!

 

 

나의 풀이

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int n;
int m;
vector<char> nobtn;

bool check(int num){
    string s = to_string(num);
    for (int i = 0; i < s.size(); ++i){
        if(find(nobtn.begin(),nobtn.end(),s[i])!=nobtn.end()){
            return false;
        }
    }
    return true;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    char a;
    for (int i = 0; i < m; ++i){
        cin >> a;
        nobtn.push_back(a);
    }

    if(n==100) {
        cout << 0;
        return 0;
    }
    int minimum = abs(n-100);

    string N = to_string(n);

    for (int i = 0; i <= 1000000; ++i){
        if(check(i)){
            // 숫자 길이(숫자버튼 누르는 횟수) + 차이(+/-버튼 누르는 횟수)를 더해준다
            int now = to_string(i).length() + abs(i - n);
            if(minimum > now) minimum = now;
        }
    }
    cout << minimum;
}