백준 1107 리모컨 파이썬

www.acmicpc.net/problem/1107

1107번: 리모컨

# 희망채널
N = int(input())
# 고장난 버튼수
M = int(input())
# 0-9 까지 버튼을 가지고 있는 리모컨
remote_controller = {str(i) for i in range(10)}

if M > 0:
#     고장난 버튼은 리모컨에서 제거
    remote_controller-=set(map(str, input().split()))

# 현재 보고 있는 채널 
current_channel = 100
# 현재 보고 있는 채널에서 보고자 하는 채널까지 +- 버튼을 통해 이동했을때 버튼을 눌러야하는 횟수
min_cnt = abs(current_channel - N)
# 498765
# 100만 채널까지 순회
# 최대 희망 채널은 50만인데 100만까지 순회하는 이유는 + 인 경우가 최적일때와 - 인 경우가 최적일때를 모두 고려하려면 100만이여야한다.
# 예를 들어, 희망 채널 400000, 고장난 버튼 [1,2,3,4,5] 인 경우, 60만 채널에서 40만 채널까지 - 로 줄이는게 최적이다.
for channel in range(1000000):
    # 현재 순회중인 채널의 각 자릿수 순회
    for j in range(len(str(channel))):
        # 현재 자릿수가 누를 수 없는 버튼이라면 해당 채널은 패스
        if str(channel)[j] not in remote_controller:
            break
        # 마지막 자릿수까지 모두 사용가능한 버튼이라면

        elif len(str(channel)) - 1 == j: 
            # 채널 번호 누른 횟수(len(str(channel)))와 
            # 채널번호에서 희망채널까지 +-를 눌러야하는 횟수를 더해서 
            # 이전에 구한 최저횟수보다 적다면 최저횟수로 지정한다.
            min_cnt = min(min_cnt, abs(channel - N) + len(str(channel)))
print(min_cnt)            

이 문제 역시 검색해봤다.

브루트포스가 익숙치 않은듯.

직접 1시간 정도 구현해보려고 이리저리 해봤는데 경우의수가 너무많아서 엄두가 나질 않았다.

케이스를 나누는게 중요한것 같다.

이문제에서는

1번 케이스: 현재채널(100)에서 그냥 희망채널까지 +- 버튼으로 이동했을 때의 횟수

2번 케이스: 모든 채널을 순회하면서 해당 채널에서 희망채널까지 +- 버튼으로 이동했을때의 횟수.

 

그리고 이 문제는 다른 블로그를 참고했는데도 이해가 안갔던 부분이,

왜 100만까지 순회하느냐였다. 최대 채널이 50만이면 50만까지만 순회하면 되지 않나 한참을 생각했다.

하지만 50만까지만 순회하게되면 작은채널부터 큰채널로 + 버튼을 눌렀을때의 횟수만 구할수 있게 된다.

큰채널에서 작은채널로 -를 했을때 최저 횟수인 경우에 대해선 알 수 없다.

예를 들어. 희망채널 400000 고장난버튼 [1,2,3,4,5] 인 경우, 

600000채널에서 - 해서 구한 경우가 최적의 해이므로 50만까지만 순회했을땐 구할 수 없다.

 

 

참.. 남이 구현해놓은걸 보면 이생각을 왜 못했을까.. 싶은데.. 혼자 생각하면 너무 막막하단 말이야..

고민하는 시간이 너무 길어지면 안좋다는 여러글을 봐서 2시간 이상 못풀면 남의 답을 봐버리는데.. 

오랜시간이 걸리더라도 직접 끝까지 풀어보는것도 필요하지 않나 싶다.