[BOJ 1107] 리모컨

문제출처

https://www.acmicpc.net/problem/1107

1107번: 리모컨

 

문제풀이

완전탐색 문제인데 약간 생각할 부분이 있었다. n의 범위가 50만까지인데 채널은 무한이기 때문에 뒤에서 탐색하는 경우 버튼을 더 적게 누를수도 있기 때문이다. 또 숫자버튼을 누르고 + 또는 -버튼 1개만 계속 눌러야 한다. 왜냐하면 +버튼을 누르다 -버튼을 누르고 다시 +버튼을 누르면 중복이 발생하기 때문에 최소값이 될 수 없기 때문이다.

이후 단순 구현만 해주면 된다.

 

소스코드

https://github.com/sw93/algorithm/blob/master/BOJ_PS/BOJ_1107/boj1107.cpp

sw93/algorithm

 

#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
bool brokenButton[10];

// 숫자버튼을 누른 채널으로 이동 가능한지 확인하는 함수
bool checkButton(int channel) {
	if (channel == 0) {
		if (brokenButton[0]) return false;
		else return true;
	}
	while (channel) {
		if (brokenButton[channel % 10]) return false;
		else channel /= 10;
	}
	return true;
}

// checkButton을 통과한 채널의 자릿수를 구하는 함수
int getChannelDigit(int channel) {
	int ret = 0;
	if (channel == 0) return 1;
	while (channel) {
		channel /= 10;
		ret++;
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	int buttonNumber;
	for (int i = 0; i < m; i++) {
		cin >> buttonNumber;
		brokenButton[buttonNumber] = 1;
	}

	int ans = 987654321;

	// 뒤에서 탐색하는게 더 효과적인 경우도 있으므로 n의 범위를 2배 늘림
	// 예를 들어 6버튼만 안고장나고 60만번 채널로 이동하고 싶은 경우
	// 초기 100번 채널에서 +버튼만 누르는 것 보다 666,666채널에서 -버튼을 누르는 횟수가 더 적음
	for (int i = 0; i <= 1000000; i++) {
		int channel = i;
		if (checkButton(channel)) {

			// 숫자버튼을 눌러 이동할때 필요한 자릿수
			int digit = getChannelDigit(channel);

			// 숫자버튼 이동과 +버튼 또는 -버튼 클릭의 합을 비교
			ans = min(ans, digit + abs(n - channel));
		}
	}

	cout << min(ans, abs(n - 100));
	return 0;
}