백준 1107 리모컨 - 파이썬

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

1107번: 리모컨

 

 

초등학교땐 맨날 달력을 찢어먹더니 이번엔 리모컨 버튼이 찢겼다.

 

현재 기준 솔브드 티어 골드5인 문제인데, 평균 시도 횟수가 4.43회이다.

예외 상황이 생각보다 많고, 나 역시도 4번의 시도 끝에 AC를 얻었다.

나의 오답 원인은 각각 달랐는데, 1. 0 버튼 처리, 2. 브루트포스 범위, 3. 오타 못찾음이었다.

꽤 재미있는 문제이다.

 

9%에서 자꾸 오답이 나오는 당신, 0 버튼이 고장났는데 누르고 있진 않은지, 브루트포스 범위를 500001까지로 설정했는 지 확인해보시면 웬만하면 걸릴겁니다.

 

 

 

 

일단 broken이라는 리스트에 고장난 버튼을 담았다.

고장 안 난 리모컨을 쓰는 경우도 있으니 이를 고려하자. BOJ가 하염없이 input을 기다리다 시간초과 날 수 있다.

 

그리고 경우의 수를 크게 두가지로 나눴다.

첫 번째는 시작 채널(100번)에서 + 나 - 버튼 만을 이용해서 목표 채널(target)까지 가는 방법이고,

두 번째는 성한 버튼으로 최대한 근처 채널까지 간 뒤, +나 -버튼을 이용해 도착하는 방법이다.

두 번째 방법을 논리만으로 해결하긴 어려워 보였는데 다행히 채널 범위가 브루트포스로 확인해볼 수 있는 수준이다.

 

일단 answer을 첫 번째 방법으로 초기화한 뒤, 0번부터 999999번까지의 채널을 모두 확인해봤다.

 

 

target의 범위가 0 ~ 500000인데 999999까지 확인하는 이유는,

내가 8 버튼만 누를 수 있는데 답이 500000인 경우를 생각해보면 된다.

범위가 500000까지라면 88888를 누른 뒤 +버튼을 411112번 눌러서, 총 버튼을 411117번 누르면 도착한다.

하지만, 범위가 999999까지라면 888888을 누른 뒤 - 버튼을 388888번 눌러서, 총 버튼을 388894번 눌러서 도착이 가능하다.

문제에서도 target의 범위는 한정했지만, 존재하는 채널의 범위는 무제한이라는 조건이 있었다.

종료값도 사실 999999보다 작아도 될텐데, 일일히 따져 주기엔 귀찮고 그냥 999999까지는 다 봐도 시간상 괜찮다.

 

 

아무튼 각각의 수를 내가 가진 리모컨 버튼으로 누를 수 있는 지 확인해주면 된다.

불가능하다면 다음 수를 탐색하고, 가능하다면 버튼 누르는 횟수를 계산해서 answer보다 작다면 갱신해주면 된다.

 

나는 고장난 버튼도 리스트안에 string으로 받고, 각 숫자를 문자열로 변환해가면서 확인했다.

이 방법을 추천하는게, 처음에는 수를 while문으로 10씩 나눠가면서 체크했더니 0번 채널일 때 while문 안으로 안들어가서 0번 버튼이 고장났는데도 예외처리가 안되는 상황을 놓쳤었다.

예외 처리 코드를 추가하면 코드가 못생겨지고, 또 다른 예외를 생각하기 싫어서 문자열 비교로 갈아탔다.

 

 

target = int(input())
N = int(input())
broken = [] # 고장난 버튼 저장
if N != 0:
    broken = list(input().split())

answer = abs(target-100) # (+)나 (-) 버튼 만으로 이동할 때

for i in range(1000000): # 0번 부터 999999까지 버튼 누를 수 있는 채널 체크
    num, j = str(i), 0

    while j < len(num):
        if num[j] not in broken:
            j += 1
        else:
            break

    if j == len(num):
        answer = min(answer, len(str(i)) + abs(i-target))

print(answer)

 

---

 

포스팅을 작성하다가 문득 궁금증이 생겨서 브루트포스 범위를 조절해서 제출해봤다.

하나의 채널을 체크할 때 연산이 10번을 넘어가지 않으니까 이론상 범위를 1000만까지 해도 되는 거 아닌가? 하는 생각에 굳이굳이 100만, 200만, 1000만으로 범위를 넣어서 돌려봤다.

 

 

100만(당연히), 200만은 통과가 됐다.

1000만은 채점만 13분이 걸렸다. 약 50%에서 시간 초과가 났다. 

 

 

야박하다..