[백준 1107번] 파이썬 - 리모컨

https://www.acmicpc.net/problem/1107

1107번: 리모컨

 

 

# 조건

• 버튼은 0~9까지의 숫자와 +, - 버튼
• + 버튼은 1채널 위로, -는 1채널 아래로, 채널은 무한대이며 0아래로는 안 내려간다.
• 이동하려고 하는 채널 N까지 최소 눌러야하는 버튼 수를 구하여라.

 

 

# 접근 방법

• 눌릴 수 있는 버튼에 한해서 제일 가까운 채널까지 이동한다.
• 이 때 누르는 버튼 수는 이동채널의 길이와 같다.
• 그 이후에는 +와 -버튼을 이용할 수 밖에 없으므로 절댓값이용해서 빼주면 된다.
• 현재 채널 100번에서 +, -만 이용하는 경우와 위에서 구한 값의 최소값을 출력해주면 된다.
• 범위를 500,000이 아닌 1,000,001 인 이유는 고장난 가고자하는 채널이 500,000이고 고장난 버튼이 1,2,3,4,5와 같은 경우 100번에서 올라가는 것 보다 600000에서 내려오는 것이 빠르기 때문.

 

 

import sys  
input = sys.stdin.readline  
  
target = int(input())  
n = int(input())  
broken = list(map(int, input().split()))  
  
# 현재 채널에서 + 혹은 -만 사용하여 이동하는 경우  
min_count = abs(100 - target)  
  
# 1000001로 설정해준다.  
# 12345 고장에 500000번 채널로 이동시  
# 100에서 가는 것보다 600000에서 내려오는 것이 빠르기 때문  
for nums in range(999901):  
    nums = str(nums)  
  
    for j in range(len(nums)):  
        # 각 숫자가 고장났는지 확인 후, 고장 났으면 break        
        if int(nums[j]) in broken:  
            break  
  
        # 고장난 숫자 없이 마지막 자리까지 왔다면 min_count 비교 후 업데이트  
        elif j == len(nums) - 1:  
            min_count = min(min_count, abs(int(nums) - target) + len(nums))  
  
print(min_count)

 

• 브루트 포스 문제를 풀 때는 항상 범위 설정이 제일 중요한 것 같다.
• 범위 설정과, 접근 방식만 잘 구현한다면 쉽게 풀리는 것 같다.