[BOJ] 1107 리모컨
https://www.acmicpc.net/problem/1107
1107번: 리모컨
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼
www.acmicpc.net
---------------------------------------------------핵심 알고리즘--------------------------------------------
브루트포스
---------------------------------------------------풀이----------------------------------------------------
특정 숫자를 누를 경우, 그 숫자에서 +나 -를 이용해서 N까지 이동해야 한다.
따라서, 맨 처음 100번과 N의 차이, 이후 버튼을 눌러 만든 숫자와 N의 차이가 핵심이다.
100번은 처음 숫자이므로 selected는 0이다. 그 상태에서 +/-를 몇 번 눌러야 하는지를 구한다.
이후 버튼을 눌러 만든 숫자 cur은 몇 개를 눌렀는지에 따라 selected가 결정되고, selected+|N-cur|이 눌러야 하는 횟수이다.
재귀함수의 종료 조건은 채널이 최대 500'000까지 있으므로 6번 누를 경우 종료하도록 하였다.
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>
using namespace std;
// broken = 0
bool button[10] = {0, };
int ans = INT_MAX;
int N, M;
// 버튼 누른 횟수 selected
void select_buttons(int cur, int selected){
if(ans > selected + abs(N-cur)){
ans = selected + abs(N-cur);
}
if(N-cur == 0 || selected >= 6){
return;
}
if(selected == 0){
cur = 0;
}
for(int i = 0; i < 10; i++){
if(!button[i]) continue;
select_buttons(cur*10+i, selected+1);
}
}
int main(void){
FASTIO;
cin >> N >> M;
for(int i = 0; i < 10; i++){
button[i] = true;
}
for(int i = 0; i < M; i++){
int tmp;
cin >> tmp;
button[tmp] = false;
}
select_buttons(100, 0);
cout << ans << "\n";
return 0;
}
---------------------------------------------------후기----------------------------------------------------
시간 제한이 널널해서 쉽게 풀었다.
만약 효율적으로 계산해야했다면, 이 방식 말고 제일 가까운 수를 만드는 방법을 따로 만들어야 했을 것이다.