[BOJ_1107] 리모컨

입력된 채널을 몇 번만에 입력할 수 있는 지 묻는 문제입니다.

그런데 제한이 있는데 바로 고장난 채널이 있을 경우 +나 -를 입력해서 대체합니다.

출력은 해당 채널로 리모컨을 돌리기 위해 누른 횟수의 최소값이 됩니다.

또한, 100번에서 시작됩니다.

그래서 99번으로 이동할 때 최소 횟수는 2번이 아니라 1번이다.

 

예를 들어

5457번으로 이동하고 싶는데 6, 7, 8번 버튼이 고장났습니다.

5, 4, 5, 5, +, +를 입력하면 이동하므로 6번입니다.

 

 

N이 500000까지이므로 음수까지 고려하면 최대 1000000번까지 리모컨을 누를 수 있게 됩니다. 백만번까지 되는 경우를 모두 확인해 보면 답을 찾을 수 있습니다.

 

기본적으로 +나 -만 사용해서 버튼을 누르는 것이 최대 값이고 이것부터 생각해 봅니다.

 

처음에는 100부터 시작하므로 정답에서 100을 빼 줘야 합니다.(음수인 경우 절대값 처리를 해줘서 양수로 만들어 줍니다) 

n=103 -> 103 - 100 => 3번

n=93 -> 93 - 100 => -7(음수이다) => 7번

 

이 수가 디폴트 값입니다. 여기서부터 더 적게 누를 수 있는 경우가 나올 수 있도록 갱신해 나갑니다. 

 

이 디폴트 값을 백만번까지 확인한 후에 최소값을 출력하면 됩니다.

 

이 디폴트 값에서 고장난 버튼이 있으면 +, -로 돌아가야하고 고장난 버튼을 만나기 전까지의 길이와 + 또는 -를 누르는 횟수를 합한 최소값이 답이 됩니다.

 

채널의 길이를 구할 때 0번 채널에 대해서는 길이로 1을 반환하도록 예외 처리를 해줘야합니다. 왜냐하면 0을 10으로 나눈 나머지는 10이기 때문입니다.

 

#include<iostream>
using namespace std;
bool broken[10];
int possible(int c) {
	if (c == 0) {
		if (broken[0]) {
			return 0;
		}
		else {
			return 1;
		}
	}
	int len = 0;
	while (c > 0) {
		if (broken[c % 10]) {
			return 0;
		}
		len += 1;
		c /= 10;
	}
	return len;
}

int main() {
	int n;
	cin >> n;
	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		int x;
		cin >> x;
		broken[x] = true;
	}
	int ans = n - 100;
	if (ans < 0) {
		ans = -ans;
	}
	for (int i = 0; i <= 1000000; i++) {
		int c = i;
		int len = possible(c);
		if (len > 0) {
			int press = c - n;
			if (press < 0) {
				press = -press;
			}
			if (ans > len + press) {
				ans = len + press;
			}
		}
	}

	cout << ans;
	return 0;
}

리모컨 문제는 이것 저것 처리해야할 if문들이 많아서 어렵습니다...ㅠ