[BOJ] 1107: 리모컨

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/1107

1107번: 리모컨

 

 처음에 시도했던 방법은 나름 꼼수를 부린 방법이었다.

 

1. 크기 10짜리 배열에 고장난 버튼을 저장해두고 채널 n을 문자열로 바꾼다.

2. string tmp="";를 선언한 후, n의 앞에서부터 해당 숫자 버튼이 있으면 바로 tmp에 추가해주고 고장난 버튼이면 다시 0부터 9까지 for문을 돌려서 목표에 가장 가까운 고장나지 않은 버튼을 추가해준다.

3. 마지막에 2에서 구한 수와 처음 n과 100과의 차이를 비교해서 답을 출력

 

 문제는 과정 2.에서 해당 목표에 가장 가까운 수가 0인 경우였다. 어찌 어찌 예외 처리를 잘해주면 통과할 듯했지만 귀찮아져서(^^..) 쌩완탐을 돌렸다.

 

 n의 범위가 0<= n <= 500000 이었고 시간 제한이 2초였기 때문에 그냥 모든 수에 대해 완탐을 돌려도 충분했다. 단, 999999까지 검사한 이유는 초기값 100에서 500000까지 + 버튼을 누르는 횟수 대략 500000번과 999999를 입력한 후 500000까지 - 버튼을 누르는 횟수가 비슷하기 때문이다.

/*
20200309
1107번- 리모컨
*/
#include <iostream>
#include <limits.h>
#include <string>
using namespace std;

int error[10];
bool hasButton(string num) {
	for (int i = 0; i < num.size(); ++i) {
		if (error[num[i] - '0'])
			return false;
	}
	return true;
}

int main() {
	int n, m, ans = INT_MAX;
	cin >> n;
	cin >> m;
	
	for (int i = 0; i < m; ++i) {
		int num;
		cin >> num;
		error[num]++;
	}

	int sum = 0; string tmp;
	for (int i = 0; i <= 999999; ++i) {
		tmp = to_string(i);
		if (hasButton(tmp)) {
			sum = tmp.size() + abs(i - n);
			if (sum < ans)
				ans = sum;
		}
	}

	if (ans > abs(100 - n))
		ans = abs(100 - n);

	cout << ans;
}