현재 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; }
