백준 1107번: 리모컨

[문제 링크]

1107번: 리모컨

---

완전탐색 문제였다.

리모컨 버튼이 0~9 번까지 있기 때문에 버튼만 가지고 만들 수 있는 채널의 범위는 0~999999 이라는 것을 알 수 있다.

i = 0 부터 999999까지 숫자에 대해 고장나지 않은 버튼으로 만들 수 있는 숫자인지 확인하고 만들 수 있는 숫자라면 해당 채널로 이동할 경우 버튼 누르는 횟수를 계산해서 최솟값을 구하면 된다.

---

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

bool number[10];

bool isMakeNumber(int num) {
	string numStr = to_string(num);

	while (!numStr.empty()) {
		if (number[numStr.back() - '0'])
			numStr.pop_back();
		else
			return false;
	}

	return true;
}

int getMinimumClick(int N) {
	int start = 100;
	int ret = abs(N - start);

	for (int i = 0; i <= 999999; i++) {
		if (i == 100) continue;
		if (isMakeNumber(i)) {
			int click = to_string(i).size() + abs(N - i);
			ret = min(ret, click);
		}
	}

	return ret;
}

int main(void) {
	memset(number, true, sizeof(number));

	int N;
	cin >> N;

	int M;
	cin >> M;

	for (int i = 0; i < M; i++) {
		int num;
		cin >> num;
		number[num] = false;
	}

	cout << getMinimumClick(N) << endl;

	return 0;
}