알고리즘 - Python / 백준 - 1107번 : 리모컨

1107번: 리모컨 (acmicpc.net)

1107번: 리모컨

 

---

풀이

• 리모컨의 고장 난 버튼이 주어질 때 , 해당 채널로 가기 위해서는 버튼을 몇 번 눌러야 하는지 구하는 문제다.
• 일단 최대 목표 번호가 500,000 이고 현재 채널 번호가 100 이므로 모든 버튼이 고장 났을 때 , +로만 움직이면 499,900번 눌러서 움직인다.
• 일단 이 부분을 생각하면서 문제풀이에 들어갔고 , 풀이 알고리즘은 2가지로 생각했다.
• 1. 멀쩡한 번호들로 모든 번호 조합을 구하고 , 해당 번호에서 목표번호까지 + , - 를 얼마나 눌러야 하는지 절댓값을 구하여 확인하는 방법
• 2. 목표번호에서 +1 , -1 씩 출발해 해당 번호를 만들 수 있는지 확인하고 만들 수 있는 번호라면 그 번호까지 얼마나 버튼을 눌러야 하는지 확인 후 최솟값이라면 갱신하는 방법
• 이번 풀이에서는 2번 방법을 사용했다.
• 어차피 100번에서 어떠한 번호로 이동할 것이라면 그 전에 +나 -를 누를 일은 없다.
• 따라서 100 -> 어떠한 번호 -> +혹은 - 만 누름 의 과정을 거치기 때문에 이 과정을 역순으로 진행하였다.
• 위에서 확인한 부분에서 최악의 경우를 생각해 보았을 때 , 시간 초과가 나지 않을 것 같다고 생각해 일단 구현해 제출해보았고 정답이 나왔다.

 

import sys
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
num = [1,1,1,1,1,1,1,1,1,1]
if m != 0:
    c = list(map(int , sys.stdin.readline().split(" ")))
    for i in c:
        num[i] = 0
df = abs(n - 100)
ori_df = abs(n - 100)
ori_check = 0
for i in range(0,ori_df):
    check_1 = 1
    check_2 = 1
    for t in str(n+i):
        if num[int(t)] == 0:
            check_1 = 0
            break
    if check_1 == 1 and df > i+len(str(n+i)):
        df = i+len(str(n+i))
    if n-i < 0:
        continue
    for k in str(n-i):
        if num[int(k)] == 0:
            check_2 = 0
            break
    if check_2 == 1 and df > i+len(str(n-i)):
        df = i+len(str(n-i))
print(df)

---