[1107] 리모컨

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

정말 고통스러웠던 문제였다. 처음에 입력받은 채널의 숫자를 각 자리별로 나눠서 고장난 번호인지 검사를 했는데 

반례가 매우 많았다.

마지막엔 브루트 포스 방식으로 풀었는데 무슨 이유에선지 자릿수를 구하는 pow()함수에서 에러가 나서 틀렸다.

멘붕에 멘붕이 거듭된 문제다.

채널이 500,000개라서,

채널이 0일때 +,-버튼으로 원하는 채널까지 이동하는 횟수

채널이 1일때 +,-버튼으로 원하는 채널까지 이동하는 횟수

.

.

.

각각 버튼이 고장났는지 검사(int possible(int n) : 고장났으면 -1, 안고장 났으면 누르는 숫자의 갯수 리턴)하면서 

계속해서 계산한다.

계산 값은 

현재 버튼에서 +,-로 이동하는 횟수(abs(N-i)) + 

현재 버튼을 누르는 횟수(possible(i)) 이다.

그중 가장 작은값을 표시한다.

이 for문은 1,000,000번을 반복하게 했는데 그 이유는 채널이 무한대이고 

500,000번 채널보다 큰 수의 채널에서 -버튼으로 내려올 경우도 있기 때문이다.

---

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

int remote[10] = { 1 }; // 고장난거

int possible(int n) { //

if (n == 0) {

if (remote[0] != -1)return 1; // 고장 안났다면

else return -1; // 고장 났다면

}

int len = 0;

int cur = 0;

while (n > 0)

{

if (remote[n % 10] == -1)

return -1;

else

{

n /= 10;

len++;

}

}

return len;

}

int main() {

int N = 0;

int M = 0;

scanf("%d", &N);

scanf("%d", &M);

int tp = 0;

for (int i = 0; i<M; i++) {

scanf("%d", &tp);

remote[tp] = -1; // 고장난건 -1

}

int cur = fabs(100 - N); // 현재에서 목표까지

int res = 0, minVal = 1000000, press = 0;

for (int i = 0; i<1000000; i++) {

press = possible(i);

if (press > 0) {

res = fabs(N - i) + press;

if (res < minVal) {

minVal = res;

}

}

}

int ret = min(minVal, cur);

printf("%d\n", ret);

return 0;

}