[백준][C++] 1107 리모컨

www.acmicpc.net/problem/1107

1107번: 리모컨

 

 

 

알고리즘 종류

완전탐색

 

 

 

사고 과정

2가지 경우가 있습니다.

1. 100에서 + 또는 -을 눌러서 채널 N에 도착하는 경우

2. 채널 N에 근접한 채널에 도착해서 + 또는 -을 누르는 경우

 

저는 채널 N에 근접한 채널을 찾기 위한 방법을 생각해서 코딩을 했지만 보증된 방법이 아니었습니다. 그래서 완전탐색으로 모든 채널에서 N에 + 또는 -로 이동한 횟수를 찾아서 최솟값을 찾으면 됩니다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
 
using namespace std;
 
 
int n, m;
int broken[10];
int ans;
 
 
bool check(int x){
    string str = to_string(x);
    for(int i=0; i<str.length(); i++){
        if(broken[str[i] - '0'] == 1) return false;
    }
    return true;
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    
    ans = abs(n-100);
    
    int x;
    for(int i=0; i<m; i++){
        cin >> x;
        broken[x] = 1;
    }
    
    for(int i=0; i<1000001; i++){
        if(check(i)){
            string str = to_string(i);
            int len = abs(n-i) + str.length();
            ans = min(ans, len);
        }
    }
    
    cout << ans << endl;
}

시행착오