문제 URL:
https://www.acmicpc.net/problem/1107
1107번: 리모컨
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼
www.acmicpc.net
위 문제는 m개의 리모컨 버튼이 고장났을 때 원하는 채널까지 최소한으로 이동하기 위해서는 몇 번 움직여야 하는지를 출력하는 문제로 브루트포스 알고리즘을 이용하는 문제이다.
먼저 +/-로만 갈 수 있는 횟수를 최솟값으로 잡아놓고 check()함수를 통해 현재 숫자가 고장난 버튼이 포함되지 않은 숫자일 경우에 최솟값과 이동 횟수 비교를 진행한다. 이때, 500,000이 넘는 숫자에서 -버튼을 통해 내려오는 경우도 있기 때문에 브루트포스를 진행하는 숫자는 1,000,000으로 잡아준다.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
vector<int> dp;
vector<bool> btn(10,false); // 0~9까지의 리모컨 버튼. true:고장남, false: 고장 안 남
bool check(int now){ // 고장난 버튼인지 확인. 고장 났다면 return false
string s = to_string(now);
for(int i = 0; i <s.length();i++){
if(btn[s[i] - '0'])
return false;
}
return true;
}
int main(){
int n, m;
cin >> n >> m;
int num;
for(int i = 0; i < m; i++){
cin >> num;
btn[num] = true;
}
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;
return 0;
}