[백준 1107번] 리모컨

[백준 1107번] 리모컨

www.acmicpc.net/problem/1107

1107번: 리모컨

 

 

 문제

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

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

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

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

 

 입력

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

 

 출력

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

 

 

 풀이

#include <iostream>
using namespace std;

int len = 0;
int result = 2147483647;
int N, M;
bool num[10] = {false,};

void ff(int idx, int val, int k){
	if(len > 1 && idx == len - 1){
		result = min(result, abs(N - val) + idx);
	}
	if(idx == len){
		result = min(result, abs(N - val) + idx);
	}
	if(idx == len + 1){
		result = min(result, abs(N - val) + idx);
		return;
	}
	
	for(int i=0;i<10;i++){
		if(!num[i]) ff(idx + 1, val + i*k, k*10);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N >> M;
	
	int NN = N;
	while(1){
		NN = NN/10;
		len++;
		if(NN==0) break;
	}
	
	for(int i=0;i<M;i++){
		int a;
		cin >> a;
		num[a] = true;
	}
	
	ff(0, 0, 1);
	if(result > abs(N-100)) cout << abs(N-100);
	else cout << result;
	return 0;
}

 생각하면서 재밌게 푼 것 같다. 먼저 원하는 채널 N의 길이를 구해주고 고장나지 않은 번호로 갈 수 있는 채널의 모든 경우를 구해보면 O(10^N의길이)이다. 문제에서 N의 범위는 최대 500000이기 때문에 O(10^6)으로 브루트 포스로 문제를 풀 수 있다. 모든 경우 대신에 원하는 채널의 길이, +-1 에서만 고려하여 조금이나마 계산과정을 줄였다. 사실 같은 길이가 아닐때는 극히 일부만 비교하면 더 최적화가 가능할 듯 한데 시간이 충분했기 때문에 그냥 넘어갔다. 

 문제를 풀면서 실수가 많았는데 첫번째로 기본 채널 100을 고려하지 않아서 틀렸습니다를 받았다. 이는 마지막에 result와 abs(N-100)을 비교해주면서 해결하였다. 이 과정에서 처음에는 100보다 작은 채널을 생각하지 않아 abs를 붙이지 않아서 두번째 틀렸습니다를 받았다.

 세번째 시도에서 24%에서인가 틀렸습니다를 받았는데 반례를 찾아보니 한자리 수의 채널일 때 len - 1의 경우는 고려하면 안되는 것이었다. 조건에 추가하니 정답입니다를 받을 수 있었다.