백준 1107 리모컨 Class 3 (Python, 완전탐색, Gold5)

백준 1107 리모컨 문제 바로가기

문제 이해

문제

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

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

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

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

입력

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

출력

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

문제 접근

처음에는 문제를 보고 목표로 하는 채널과 가장 가까운 채널을 찾고 그 채널과 목표채널의 차이를 구하면 된다고 생각했다.
하지만 이렇게 되면 예외가 많이 발생하는 문제점이 있었다.
문제에 시간초과 제한이 2초임을 확인했고, 목표로 하는 채널은 500,000이 최대임을 확인했다. 컴퓨터가 1초에 1억번의 계산을 하기 때문에 완전탐색으로도 충분히 시간초과되지 않을 것이라고 생각했다.

따라서 완전탐색으로 진행했다.

• 숫자 누르기
• +or-
• 횟수

문제 풀이

숫자 누르기

숫자를 0부터 1000000까지 모두 다 누른다고 생각하여 for문을 진행해준다.
miss에 있는 숫자를 눌렀다면 break를 통해 result 계산을 하지 않도록 한다.

for i in range(1000000):
    for j in str(i):
        if int(j) in miss: # 만약에 고장나서 누를 수 없는 숫자라면
            break # 취소
    else:
    #그게 아니라면 전에 구한 result와 현재 숫자의 result중 작은 값을 result에 저장
        result = min(result, len(str(i))+abs(N-i))

+or-

for i in range(1000000):
    for j in str(i):
        if int(j) in miss:
            break
    else:
        result = min(result, len(str(i))+abs(N-i)) # +or-로 구하는 법은 단순 계산이다.

횟수

누르는 횟수의 초기값은 처음시작인 100에서 +or-로 목표인 N까지 이동하는 값을 초기값으로 잡았다. 목표에서 시작의 차를 구하고 절대값을 씌우면 +or-로 이동한 값이 구해진다.

result = abs(N-start)

제출 코드

import sys
from collections import deque
start = 100
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
if M != 0:
    miss = list(map(int, sys.stdin.readline().split()))
else:
    miss = []
result = abs(N-start)
for i in range(1000000):
    for j in str(i):
        if int(j) in miss:
            break
    else:
        result = min(result, len(str(i))+abs(N-i))

print(result)

# 숫자 누르기
# + or -
# 횟수