[BOJ] 1107. 리모컨

리모컨 성공분류

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	32667	7526	5142	22.378%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1 

5457
3
6 7 8

예제 출력 1 

6

예제 입력 2 

100
5
0 1 2 3 4

예제 출력 2 

0

예제 입력 3 

500000
8
0 2 3 4 6 7 8 9

예제 출력 3 

11117

힌트

5455++ 또는 5459--

풀이

알고리즘 분류 : 브루트 포스 (완전탐색)

처음 접근했던 방식은 최대한 답에 근접한 채널까지 누를 수 있는 버튼을 눌러 접근하고나서 +/-를 이용해 답을 출력하는 로직이었다. 하지만 반례가 너무 많아서 정리가 되지 않아서 힌트를 찾아본 결과 입력값의 최대값이 500,000 으로 크지 않기 때문에 완전탐색으로 풀어도 시간초과가 나지 않는 범위이기 때문에 수많은 반례를 모두 나누기보다 무식하게 모두 탐색하는것이 문제 풀이를 빨리 할 수 있는 방법이되겠다. 

범위가 1,000,001 까지 인 것은 주어지는 target 채널의 범위는 500,000 이지만 그 범위를 넘어선 채널로 이동해 - 버튼을 누르는 경우가 있기 때문이다. 0부터 최대범위까지의 수를 체크하면서 고장난 숫자를 포함하는 경우가 아니라면 버튼 누르는 횟수를 구해 최솟값을 계속해서 갱신해갔다. 이때 ans의 초기값은 현재 채널 100 번에서 +/-만을 누르는 경우의 버튼 누르는 횟수로 지정했다.

브루트 포스는 말이 쉽지 구현해 내는건 쉽지가 않다. 그리고 문제가 주어졌을때 이렇게 하나씩 다 풀어도 될까?  싶은 마음을 이기고 모두 구현하는 판단을 내리기 아직 너무 어려운것 같다. ㅠㅠ 하지만 모든 경우에 100만번의 연산만이 이루어지기 때문에 시간복잡도는 예상외로 O(1)일 수 있다는 블로그 글을 확인했다. 알고리즘은 참 어렵다..

코드

target = int(input()) brake_num = int(input()) broken = [] if brake_num:     broken = list(map(int,input().split())) def remote(target,broken):     current = 100     # 위/아래 버튼만 누르는 경우     ans = abs(target-current)     for i in range(1000001):         temp_list = [int(j) for j in str(i)]         if all(j not in broken for j in temp_list):             temp = len(str(i))             temp += abs(i-target)             ans = min(ans, temp)     return ans print(remote(target,broken))

cs