BOJ 1107 리모컨

처음 문제를 봤을때 무식하게 이동하려는 채널의 자릿수를 확인하면서 누를 수있는 버튼중 차이가 가장 작은것을 선택할 생각을 하였다. 하지만 다음 입력 예제를 가지고 생각해 보았을때 처음 생각한 방법으로 답을 구할 수 없는 것을 할게 되었다.

 

500000

6

0 2 3 6 7 8

 

위의 입력으로 버튼을 눌러서 500000과 최대한 가깝게 이동할 수 있는 곳은 499999 이다. 하지만 처음 생각한 방법으로 각자리의 차가 가장 작은것을 선택하게 된다면 511111이 된다. 이럴 경우 정답은 7인데 오답 11117이 나오게 된다.

이를 해결 하기 위해 각 자리마다 경우의 수가 붙게 되는데 이를 찾는 것 뿐만 아니라 구현하는 것도 왠지 이 방법으로 문제를 풀었다고 해도 어디선가 반례가 나올것 같았다.

 

여기서 생각한 방법은 고장난 버튼 조건 적용하여 숫자를 0 부터 500000 까지 하나씩 확인하고 차이가 가장 작은 수가 우리가 찾는 버튼으로 이동할 수 있는 최적의 값이라는 것을 알게 되었다. 하지만 탐색 범위를 500000 까지로 설정하면 안된다. 이동하는 채널이 500000 이지만 리모컨으로 이동할 수 있는 범위는 무한이된다. 그래서 500000을 기준으로 범위를 두배로 설정하여 1000000까지로 제한해주었다. 

 

대충 시간복잡도를 계산해보면 리모컨 숫자 10개, 범위 1000000가 되고 부르트포스로 문제를 풀었을때 O(10000000) 이정도면 1억이 안되니 시간안에 풀수 있을것 같다고 생각했다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;

int n, m, minCnt;
bool button[10];

void solution()
{
	minCnt = abs(n - 100);

	for(int i = 0; i < m; i++)
	{
		int num;
		cin >> num;

		button[num] = false;
	}

	if(n == 100)
	{
		cout << 0;
		return;
	}

	int result = 0;
	int num = 987654321;
	int answer = 987654321;
	string s;
	for(int i = 0; i <= 1000000; i++)
	{
		s = to_string(result);

		bool isOk = true;
		for(int j = 0; j < s.size(); j++)
		{
			if(!button[s[j] - '0'])
			{
				isOk = false;
				break;
			}
		}

		if(isOk)
		{
			if(answer > abs(n - result))
			{
				answer = abs(n - result);
				num = result;
			}
		}
		result++;
	}
	int tmp = (int)(answer + to_string(num).size());
	minCnt = min(minCnt, tmp);
	cout << minCnt;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	memset(button, true, sizeof(button));

	cin >> n >> m;
	solution();
}