[BOJ 1107] 리모컨

문제 링크 : https://www.acmicpc.net/problem/1107

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

제한

시간 제한	메모리 제한
2sec	256MB

힌트

예제 1의 경우 5455++ 또는 5459--

---

풀이

목표 채널 $N$에 도달하기 위해 리모컨 버튼을 최소로 누르는 방법을 찾는 문제이다. 이동 방법은 크게 두 가지로 나뉜다.

1. 숫자 버튼을 사용하지 않고 이동: 현재 채널인 100번에서 + 또는 - 버튼만 눌러서 이동하는 경우.
2. 숫자 버튼으로 특정 채널 이동 후 버튼 조작: 고장 나지 않은 숫자 버튼으로 목표와 가까운 채널 $i$로 점프한 뒤, $N$까지 +나 -로 이동하는 경우.

이 문제의 핵심은 “어떤 채널로 점프해야 가장 적게 누를 것인가”를 결정하는 것이다. $N$의 범위가 $500\,000$ 이하로 작기 때문에, 모든 가능한 채널을 탐색하는 브루트포스(Brute Force) 접근법이 유효하다.

• 탐색 범위: $N$은 $500\,000$까지이지만, 더 큰 채널에서 내려오는 것이 빠를 수도 있으므로 약 $1\,000\,000$까지의 채널을 검사한다.
• 유효성 검사: 해당 채널 번호를 구성하는 모든 숫자가 고장 나지 않은 버튼인지 확인한다.
• 최솟값 갱신:
  • 초기값은 abs(N - 100)으로 설정한다.
  • 유효한 채널 $i$를 찾으면, (i를 누른 횟수) + abs(N - i)를 계산하여 기존 최솟값과 비교한다.
• 최적화: 만약 현재 검사 중인 채널 $i$가 $N$보다 크면서 이미 유효한 채널을 찾았다면, $i$가 더 커질수록 $abs(N - i)$ 값은 무조건 증가하므로 탐색을 종료해도 무방하다.

모든 버튼이 고장 난 경우나 이동하려는 채널이 100번인 경우 등 예외 상황을 고려하여 구현하면 문제를 해결할 수 있다.

소스코드

Github Link : Source Code

참고 알고리즘 : 브루트포스 알고리즘