[백준 알고리즘/Python] 1107 리모컨

문제

 

문제 이해

처음에 실제 리모컨 누르는 로직을 생각했습니다.

ex) 5457중에 6,7,8이 고장났다.

5 누르고 -> 목표 값과의 최소 확인

54 누르고 -> 목표 값과의 최소 확인

545 누르고 -> 목표 값과의 최소 확인

5457 누르고 -> 목표 값과의 최소 확인

이렇게 접근을 했는데 로직이 복잡해지고 만약 고장난 수를 제외하면 모든 수를 파악할 수가 없었습니다.

 

다른사람의 풀이를 참고했을때 허망함을 느꼈습니다. 그냥 0~1,000,000까지 수열을 돌리고 그중에 고장난 버튼수를 제외합니다. 그리고 목표값과 거리가 가장 작은 수를 찾습니다.

이게 부르트포스 인가.. 하고 느꼈습니다.

 

근데 채널의 수는 0~ 500,000까지 인데 1,000,000을 넣는가?

수빈이가 이동하려는 채널은 0~ 500,000까지, 채널의 수는 무한대 수빈이는 500,000에 가려면 500,001 채널에서 -를 누를 수도 있습니다.

 

ex) 만약에 수빈이가 이동하려는 채널이 500,000이고, 리모컨의 숫자 중 1, 2, 3, 4, 5가 고장났다고 가정해봅니다.

이 때, range의 범위가 500,000으로 제한되면, 시작점인 100번에서 +만 눌러서 500,000까지 도달하는 총 499,900번 버튼을 클릭합니다. 이것은 최적의 해가 아닙니다.

600,000에서 -를 100,000번 눌러 target에 도달하는 것이 최적의 해입니다.

이러한 이유 때문에 range는 1,000,000까지로 설정해주어야 한다.

 

참고

https://seongonion.tistory.com/99?category=852500