리모컨
문제의 원본은 여기서 확인하세요.
- 브루트 포스
기존 채널 100에서 시작하는 경우, 목표 채널과 가장 가까운 채널로 이동한 후, - 혹은 +로 이동하는 경우 중 최소의 이동횟수를 찾는다.
목표 채널과 가장 가까운 채널을 찾기 위해 Brute Force 방식으로 찾는다. 목표 채널의 최대값이 500000임으로 7자리의 수 이상은 찾을 필요가 없다.
따라서 0 부터 1000000까지 모든 경우의 수에서 가장 가까운 채널에서 이동한 경우 목표 채널까지 이동하는 이동 횟수를 구한다.
이중 최솟값이나 100에서 이동한 경우중 더 작은 값이 해가 된다. 여기서 유의해야할 점은 주어진 수의 자리수를 구하거나 버튼이 고장여부를 확인 할때 0에 대해서 예외처리를 해주어야 한다는 점이다.
// 0에 대한 예외처리를 확실하게 해주어야 한다.
#include <iostream>
#include <cmath>
using namespace std;
bool broken[10];
// check given number is usable or not
bool isPossible(int n) {
if (n == 0) {
return !broken[0];
}
while (n > 0) {
if (broken[n % 10]) {
return false;
}
n /= 10;
}
return true;
}
// count number of digists
int getNumOfDigits(int n) {
if (n == 0) {
return 1;
}
int count = 0;
while (n > 0) {
n /= 10;
count++;
}
return count;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int N, M;
cin >> N >> M;
// make true at given broken number index
for (int i = 0; i < M; i++) {
int brokenNum;
cin >> brokenNum;
broken[brokenNum] = true;
}
// when start from default channel 100
int minimum = abs(N - 100);
int temp;
for (int i = 0; i <= 1000000; i++) {
if (isPossible(i)) {
temp = abs(N - i) + getNumOfDigits(i);
minimum = min(minimum, temp);
}
}
cout << minimum << endl;
return 0;
}