백준 알고리즘 - 리모컨 (1107) [Python]

 

 

 문제

 

www.acmicpc.net/problem/1107

1107번: 리모컨

 

 

 

 

 

 문제 상황

 

- 리모컨으로 목표 채널에 도달하기 위해서 필요한 최소 이동 횟수를 출력한다.

 

 

 

 

 

 

 해결 전략

 

- 문제 상황 그대로를 시뮬레이션하여 최소 이동 횟수를 비교한다.

 

 

 

 

 

 

 코드

 

from sys import stdin
input = stdin.readline
target = input().strip() # 가고 싶은 채널
broken_num = int(input()) # 고장난 채널 개수
broken = list(map(int, input().split())) # 고장난 채널 번호
button = [i for i in range(0,10) if i not in broken] # 고장나지 않은 채널 번호
# +, - 로만 채널 이동하는 경우
min_cnt = abs(100-int(target))
# 숫자로 이동하는 경우
for num in range(1000000):
    num = str(num)
    for i in range(len(num)):
        if int(num[i]) not in button: break
        elif i == len(num)-1:
            min_cnt = min(min_cnt, len(num)+abs(int(num)-int(target)))
print(min_cnt)
 
# 틀림
closest = "" # 버튼으로 접근 가능한 가장 가까운 수
if broken_num == 10 :
    print(abs(int(target)-100))
else :
    for i in range(len(target)):
        diff = 0 # 관찰할 차이
        while True:
            if int(target[i])+diff in button:
                closest += str(int(target[i])+diff)
                break
            elif int(target[i])-diff in button:
                closest += str(int(target[i])-diff)
                break
            diff += 1
    withoutbutton = abs(100 - int(target))
    withbutton = len(target) + abs(int(target)-int(closest))
    print(min(withoutbutton, withbutton))

 

 

 

 

 

 

 

 해설

 

- 아래에 틀림 코드는 상황 자체를 시뮬레이션해서 상황을 가정하여 결과를 출력했지만 5%에서 틀렸습니다 가 나왔다. 

 

- 어떤 수를 기준으로 반복할 것이냐가 포인트인데 string으로 target 숫자를 관찰하며 시뮬레이션 할 수도 있지만 이 문제는 brute force를 사용하였다. 조건이 500000이므로 최대 1,000,000까지 관찰하며 번호를 누른 후 이동할 수 있는 모든 경우를 계산한다. if문으로 상황을 쳐내려가는게 아니라 숫자 자체를 관찰하므로 고장난 버튼이 들어잇는 경우는 무조건 제거하고 전부 가능한 버튼들이라면 min_cnt를 갱신하며 반복한다.

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- brute force를 두려워하는 경향이 있다. 전수조사를 고려하고 다른 방법을 고려하는 습관을 들이자.

 

- 포인트를 목적이 아니라 후보군으로 둬서 여러번 반복하는 관점을 가질 필요가 있다. 반복을 무서워하지 말자.