[AC] 1107 리모컨

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/1107.cpp

이 문제는 과거에 내가 틀렸던 문제이다. 그리고 최근에 다시풀어봤는데... 

우선 나의 생각은 이러했다.

1. 현재 채널이 100번이기 때문에 오직 +와 -만 사용하여 카운팅수를 구해본다.

2. 근사치를 이용한다. 즉 3 4 5 번이 고장났는데 45번을 눌러야한다면 근사치인 29번과 60번을 눌러 플러스 마이너스를 통해 구해본다.

3. 자리수변경의 경우를 고려해본다. 즉 999번을 누르고싶은데 9번이 고장났다면 자리수를 변경시켜 1000을 만들고 마이너스를 하면 간단한 문제이다.

위 3가지 경우를 전부 구해서 3개중 가장 적은 값을 출력하게 하면 답이나오겠다 생각했다.

그런데 문제를 가만보니 최대인풋이 50만이다. 즉 for문을 돌려 모든 수를 대입해봐도 시간내에 풀린다는 말이 될것이다.

그래서 포문을 돌려 금지된 수가 있는지 체크하고 없다면 플마를 대입해서 최소값을 구하게 했다. 그런데 예제의 마지막경우엔 50만을 넘어서는 입력을 해야만한다. 그래서 나는 100만까지 해보라고했다. 어차피 100만도 시간내에 충분하다. 그랬더니 간단히 정답이 나왔다.

역시 알고리즘문제는...생각을 어떻게 하느냐의 차이이다. 

아무리 좋은 기술과 지식을 가지고있어도 간단히 생각해서 간단히풀면 그게 더 좋은 알고리즘이라고 생각한다.