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

문제 링크

1107번: 리모컨

문제 요약

0 ~ 9까지 숫자와 +, - 버튼을 가진 리모컨이 있다. 이 리모컨 버튼 중의 일부는 고장난 상태이다. 고장난 버튼아 주어졌을 때, 원하는 채널로 가기 위해 버튼을 눌러야 하는 최소 횟수를 구해야 한다.

접근 방법

9000명 이상이 푼 웰노운 문제입니다. 정답률이 낮아서 함정이 좀 있을까 했는데 기우였습니다. 기본적으로 브루트포스 알고리즘으로 풀 수 있습니다.

일단 숫자 버튼을 누르기 않고 이동할 수 있는 횟수를 구합니다. 현재 채널은 100번이기 때문에, $|N-100|$이 그 값이 됩니다. 이제 0부터 1000000까지 이동하면서, 고장난 버튼이 있어 만들 수 없는 수는 제외합니다. 1000000까지만 제외하는 이유는, N이 500000에 근접할때, 1000000을 넘어가는 큰 수들은 100에서 직접 이동하는 것보다는 더 멀리있기 때문입니다. 이제 나머지 수들로 목표 채널을 만드는데 드는 비용을 계산하고, 그 비용의 최솟값을 구하면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	int n, m;
	cin >> n >> m;

	vector<int> v(m);
	for (int i = 0; i < m; i++)
		cin >> v[i];

	int res = abs(n - 100);
	sort(v.begin(), v.end());
	for (int i = 0; i <= 1000000; i++)
	{
		string str = to_string(i);
		bool flag = false;
		for (auto& j : str)
		{
			if (binary_search(v.begin(), v.end(), j - '0'))
			{
				flag = true;
				break;
			}
		}

		if (!flag)
			res = min(res, abs(n - i) + (int)str.size());
	}

	cout << res;
	return 0;
}