(c++)백준 1107번: 리모컨

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

1107번: 리모컨

[풀이]

brute force로 풀었다.

1. 0~INF 모든 수 중 고장난 버튼을 누르지 않아도 되고, 이동하려고 하는 채널과 가장 가까운 수를 찾기

2. 1)에서 찾은 수의 길이+이동하려고 하는 채널과의 차이와 현재 채널인 100과 이동하려고 하는 채널의 차이를 비교했을 때 더 작은 수를 출력

누를 수 있는 수인지 확인할 때 0인 경우를 따로 처리해 줘야 한다. ∵ while문은 num이 0이 아닌 경우에만 돌기 때문에

N은 500,000까지이지만, 5,6,7,8,9를 누르지 못할 경우도 생각해야 하므로 INF를 1,000,000 + 1로 잡았다.

 

#include <iostream>
#include <string>
#include <cstdlib>//abs
#include <algorithm>//min
using namespace std;

int INF = 1000001;
int noButton[10];//1이면 고장난 버튼

//누를 수 있는 번호인지
bool Possible(int num) {
	//누르려는 번호가 0인 경우 따로
	if (num == 0) {
		//버튼 0이 고장난 경우
		if (noButton[0] == 1)
			return false;
		else
			return true;
	}
	while (num) {
		//고장난 버튼의 번호가 포함되어 있으면 false반환
		if (noButton[num % 10] == 1) {
			return false;
		}
		num /= 10;
	}
	return true;
}

int getMinimum(int num) {
	//현재 채널인 100에서 + 또는 -버튼으로 보려는 채널로 가는 경우
	int From100 = abs(num - 100);
	int Min = INF;
	int tmp;
	for (int i = 0; i <= INF; i++) {
		//누를 수 있는 번호면
		if (Possible(i)) {
			//번호 길이
			tmp = to_string(i).length();
			//+-누르는 횟수
			tmp += abs(i - num);
			//최솟값 갱신
			Min = min(Min, tmp);
		}
	}
	//100에서 +,-로 접근하는 것과 비교
	return min(From100, Min);
}

int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int n;
		cin >> n;
		noButton[n] = 1;
	}
	cout << getMinimum(N) << endl;
	return 0;
}