[BOJ] 1107 : 리모컨 [브루트포스](Python)

문제 링크

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

1107번: 리모컨

소스 코드

import sys
input = sys.stdin.readline

n = int(input().rstrip())
m = int(input().rstrip())
if m: broken = list(map(int,input().rstrip().split()))
else: broken = []

gap = abs(n-100) # +,- 로만 이동할 경우

for num in range(1000001): # 100만 범위의 숫자들에 대해
    num = str(num)
    for i in range(len(num)):
        # 그 숫자의 일부가 망가진 번호인 경우 패스
        if int(num[i]) in broken: break
    # 망가진 번호 없는 경우 '목표 번호 - 숫자 + 자릿수'
    else: gap = min(gap,abs(n-int(num))+len(num))
    
print(gap)

 

해설

• for문의 범위는 1,000,000까지
• 자릿수 반영

원래 브루트포스 유형이 다 이렇지는 않았던 것 같은데... 뭔가 그리디처럼 풀 수는 없는가 고민을 꽤 해봤다.

불가능할 것 같지는 않은데 거의 구현유형 이상으로 풀이가 지저분해지는 느낌이었다.

위 소스 코드에 관한 여러 풀이들처럼 이 문제에서 가장 중요한 것은 범위 설정인 것 같다.

 

for문의 범위

for 반복문의 범위를 백만까지로 설정함으로써 특정 숫자에서 더하거나 빼거나 해서 500,000까지 도달할 수 있게 만드는 것이다. (목표 채널 범위가 500,000까지 이므로 0에서 출발할수도 있고 1,000,000에서 출발할 수도 있다.)

 

또한 자릿수도 반영해야 한다.

이게 참 문제가 설명이 너무 대충이라 맘에 안드는데(백준은 이런 문제들이 많은 것이 문제점인듯) 리모컨의 망가지지 않은 버튼을 클릭할 때마다 카운트가 올라간다.

따라서 다섯 자리 숫자였다면 다섯 번을 클릭하는 것이 디폴트고 여기서 추가로 + 혹은 -를 눌러 목표하는 채널 숫자 n까지 변경해야 하는 것이다.

 

for else문

for else 형태에 익숙하지 않은 분들도 있을 것 같다. 이는 for 반복문을 돌리면서 break 등으로 끊기지 않은 경우에만 else가 발동하도록 되어있다.

여기서는 num을 구성하는 어떤 숫자가 망가진 번호에 포함되면 break 한다.

따라서 어떤 숫자도 broken에 포함되지 않은 경우에만 else 문을 만나서 gap을 갱신하도록 되어있는 것이다.