BOJ 1107

리모컨이라는 문제이고, 수업시간에 완전탐색 부분에서 배운 문제이다.
리모컨에는 0~9, +, -  버튼이 있고, 0~9버튼 중에 몇개가 고장 나있을 수 있다.
그리고 현재 채널은 100이다.
자 이제 여기서 원하는 채널을 입력받고 그 채널까지 가는데 버튼을 눌러야하는 최소 횟수를 구하는 것이 문제이다.

이것을 풀기위해서 일단, 버튼을 최소로 누르기 위한 규칙을 살펴보자면
1. 숫자 버튼을 누르고 +, -버튼을 누르고 또 숫자 버튼을 누르면 이전에 누른 버튼들은 아무런 의미가 없게 된다. 그러므로 항상 버튼을 눌러야하는 횟수를 최소로 하려면 숫자부터 누르고 +, -를 눌러야한다.
2. 그리고 +와, -를 같이 쓰는 것은 아무것도 안한 것과 같을 수 있다. 그러므로 버튼을 눌러야하는 횟수를 최소로하려면 +, -중 하나만 써야한다.

그리고 마지막으로 숫자 버튼을 아예 누르지않아도 되는 경우와도 비교해봐야한다.
100에서 더 가까우면 +, -중 하나만 누르면 될 것이다.

자 일단 그래서 원하는 채널과 가장 가까운 채널을 찾아서 그 차이의 절대값만 구하면 될 것 같은데, 문제는 가장 가까운 채널을 어떻게 찾을 것이냐?
난 일단 고장난 버튼을 제외하고 원하는 채널과 같은 버튼이나 가장 가까운 수의 버튼을 선택하는 방식을 택했다.
예를들면 1234 가 있다면 1, 2, 3, 4로 분해해서 1과 가장 가깝거나 같은 버튼을 선택한다
만약 1이 고장 나있다면 0 혹은 2가 선택된다. 그다음은 2혹은 2와 가장 가까운 버튼을 선택한다. ...이런식으로 하면 4자리 수인 경우 2의 4제곱 개의 수가 나오는데, 원하는 채널과 가장 가까운 수를 그 수들 중에서 고르는 방식으로 하려고 했다.

근데 막상 해보려니 내 실력부족으로 인해... 겨우 구현은 했고, 주어진 예제는 맞았지만 결국 틀렸다.
어디서 틀렸을까?
생각해보고, 다른 예제들을 내가 만들어보았는데, 내 알고리즘에는 허점이 있다.
원하는 채널과 가장 가까운 채널을 찾는것에 허점이 있었다.

나는 각 자리별로 수를 분해해서 그 수와 같거나 가장 가까운수를 선택하는 방식으로 가장 가까운 채널의 수를 찾으려고 했는데, 이럴 경우 어떤 문제가 발생하는지 한번 예제를 보자.
19768
3
3 5 9
이렇게 19768이라는 채널이 주어지고, 고장난 버튼은 3, 5, 9 이렇게 3개라고 하자.
자 내 알고리즘에 따르면 1, 9, 7, 6, 8 각각에 대해서 가장 가깝거나 같은수를 선택할 것인데,
그렇다면 1, 8, 7, 6, 8이 선택될 것이다. 그러고보니 9와 가까운 수를 선택할때 0은 선택을 안하고 8만 선택하게 만들어놨네... 지금 글 쓰면서 깨달았다. 여튼...
19768에 대해서 18768이 가장 가까운 수로 선택되었는데... 확실히 아니다. 18768보다 가까운 수가 더 있다. 18868도 있고, 18888도 있고.. 아마 가장 가까운 수는 20000일 것이다.

백준님 강의자료와 강의에 따르면 아마 백준님은 가장 가까운 수를 모르기때문에 어떻게 구할 것인가 하시면서 문제에서 주어진 조건이 이동하려는 채널은 0<= N <=500,000 이므로 50만개를 다 보면된다고 하시는 것 같다. 그리고 이게 완전 탐색이고... 또 시간제한이 무려 2초라.. 50만개를 다보는 건 전혀 문제 될 것 없다.(참고 : 대충 1초 = 1억번 연산으로 간주...)

휴... 처음부터 풀이를 안보고(아 물론 몇주전에 풀이 수업을 듣긴했지만 어느정도 기억이 안나는 상태에서 풀어서 ...) 내가 풀어보고 이렇게 풀이를 보니까 확실히 문제에 대한 이해도가 높아지고 풀이 하나하나가 진짜 마음에 와닿는다.

셜록홈즈의 말에 따르면 천가지 정도의 범죄만 외우고 있어도 웬만한 범죄는 해결할 수 있다고...(확실하진 않지만 이렇게 말한 것 같다) 그래서 나도 알고리즘 문제를 최대한 많이 접하기위해 풀이를 먼저 보고 여러번 반복해서 숙달할까 생각했는데, 이것도 좋은 것 같고, 고민을 오래하는 것도 좋은 것같고 그래서 지금 두 방법을 섞어서 하는 중이다.

아직 100문제도 못풀었는데, 한달에 400문제씩 풀고 이런 사람들 보면 참 난 휴학까지 해놓고 뭐하는 건가 이런 생각도 들지만 아직 얼마 안되기도 했고, 초반이기도 하고 꾸준히 내 방식대로 가봐야겠다. 일단은.