<Baekjoon> #1107 리모컨 (Remote Control Problem) c++

현재 100번 채널에 있다. 이동하려고 하는 채널 N이 5457이고 6,7,8 번 버튼이 고장났을 경우에는 5455번으로 이동하고 + +. 총 6번의 버튼을 누르면 된다.

즉, 크든 작든 제일 가까운 숫자로 가서 +,- 로 이동해야한다.

처음에는 수학적으로 접근해서 일의 자리부터 원래 N의 일의 자리와 오차범위가 가장 작은 숫자를 하나씩 찾으려는 이상한 생각(?)을 했다.

문제 풀이는 brute force 로 풀면 간단하지만 생각해야할 것들과 코드가 조금 정신이 없다..

1. 고장난 버튼의 숫자를 입력 받으면서 고장난 숫자에는 1의 값을 넣어준다. (bool broken[i]=true)
2. 먼저 N에서 가까운 숫자부터 작아지는 경우와, 커지는 경우로 나누어 생각했다. (최대한 연산 속도를 줄이기 위해)

2-1. N에서 가까운 숫자부터 작아지는 경우

check()함수 에서는 i가 숫자 버튼으로 누를 수 있는 숫자인지 확인한다.
만약 누를 수 있다면 숫자 i 의 길이와 (길이는 string 형으로 변환해서 구하는게 간단하다) + 숫자 i 와 이동하려는 채널간 차이 (abs(i-n))의 합을 구한다.

원래 ret에는 이동하려는 채널과 현재 채널 100의 차이가 저장되어 있다. 즉, 전부 +나 -로 이동하는 경우가 저장되어있다.

둘 중 작은 값을 ret에 다시 저장한다.

그러고 i값이 존재하는 경우 바로 break해서 반복문을 빠져나온다. 가장 가까운 숫자를 구하면 되므로 더 이상 할 필요가 없다.

2-2. N에서 가까운 숫자부터 커지는 경우

코드는 2-1의 경우와 동일하다. 여기서는 i의 값이 n보다 항상 크거나 같으므로 굳이 abs연산은 쓰지 않아도 됐었다.

MAX는 1000000으로 설정해 두었는데 이동하려는 채널의 최댓값은 500000이지만 5,6,7,8,9의 숫자가 고장날 경우도 있기 때문에 2배로 설정했다. 이 부분이 제일 이해하기 어려웠다.

3. check()에서는 while 문을 돌며 일의 자리부터 차례대로 고장난 숫자가 있는 지 없는지 검사한다.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;
int n, m;
const int MAX = 1000000;
vector<bool>broken(10);

void input() {
	cin >> n >> m;

	int k;
	for (int i = 0; i < m; i++) {
		cin >> k;
		broken[k] = true;
	}
}


bool check(int k) {

	if (k == 0)
		return broken[0] ? false : true;

	while (k) {
		if (broken[k % 10] == 1)
			return false;
		k /= 10;
	}
	return true;
}

int solution() {

	int ret = abs(n - 100);
	int tmp;

	if (m == 10)
		return ret;

	for (int i = n; i>=0; i--) {
		if (check(i)) {
			tmp = to_string(i).length() + abs(i - n);
			ret = min(ret, tmp);
			break;
		}
	}

	for (int i = n; i <= MAX; i++) {
		if (check(i)) {
			tmp = to_string(i).length() + abs(i - n);
			ret = min(ret, tmp);
			break;
		}
	}

	return ret;
}
int  main() {
	input();
	cout << solution() << endl;

	return 0;
}