[Gold 5] 1107번 리모컨

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

1107번: 리모컨

 

이 문제는 브루트포스를 사용해서 해결해야 한다.

 

브루트포스는 완전탐색 알고리즘이다.

즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.

 

알고리즘 방식

 ① 주어진 문제를 선형 구조로 구조화한다.

 ② 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.

 ③ 구성된 해를 정리한다.

 

문제에서 사용한 브루트포스는 다음과 같다.

1. 현재 찾고자 하는 체널과 현재 보고 있는 체널인 100의 차의 절대 값을 min 값으로 저장한다.

2. 0부터 1000000만큼 반복한다. 

3. i를 문자열로 바꾸고 고장난 버튼에 해당하는 수가 있는지 확인한다.

   - 이는 문자열 순회를 통해 48(0)을 빼서 고장난 버튼에 접근할 수 있다.

4. 고장난 버튼에 접근하지 않은 숫자이면, 찾고자 하는 체널와 현재 수의 차와 현재 수의 자릿수를 더해 저장한다.

5. 저장한 값이 최소 값이면 입력한 버튼 수가 된다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>

using namespace std;


vector<int> dp;
vector<bool> mal(10,false);

bool check(int now){
    string s = to_string(now);
    for(int i = 0; i <s.length();i++){
        if(mal[s[i]-48]){
            return false;
        }
    }
    return true;
}

int main(){
    int n,c;
    cin>>n>>c;
    int tmp;

    for(int i = 0; i < c; i++){
        cin>>tmp;
        mal[tmp] = true;
    }
    string st = to_string(n);

    int minimum = abs(n-100);
    for(int i = 0; i <= 1000000; i++){
        if(check(i)){
            int tmp = abs(n-i)+to_string(i).length();
            minimum = min(minimum,tmp);
        }
    }
    cout<<minimum<<endl;


    return 0;
}