Baekjoon 1107번 리모컨

문제

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

걸린 시간

02 : 20 : 03 실패

풀이

Python3

import sys
input = sys.stdin.readline

def solve(channel):
    global push 
    for i in btn:
        now = channel + str(i)
        push = min(push, len(str(int(now))) + abs(N-int(now)))
        if len(now) < 6:
            solve(now)

if __name__ == "__main__":
    N = int(input())
    M = int(input())
    push = abs(N-100)

    # 고장난 버튼이 없을 경우
    if M == 0:
        # +, - 로 채널을 이동, 숫자로 이동 중 최소값
        push = min(push, len(str(N)))
    else:
        broken = set(map(int, input().strip().split()))
        btn = set(i for i in range(0, 10))-broken
        solve('')    

    print(push)

나름 풀이 전략을 짜고 구현도 생각한대로 잘 되서 쉽게 성공할 줄 알았다.

결과는 원인 모를 런타임 에러와 수많은 반례가 존재했다. 2시간 넘게 고민을 하다 결국 답을 보니 브루트 포스 문제였다.

모든 경우의 수를 테스트해 보아야 하는 문제였지만 여러 경우에 맞게 조건을 추가, 변경하다 보니 코드는 점점 더러워지고 에러가 나는 부분은 더 찾기 어려워졌던 것이다.

런타임 에러 때문에 고생을 많이 했는데 1시간을 넘게 용을 써도 찾지 못했던 부분은 다음과 같다.

1. 비어있는 리스트의 인덱스 참조
2. 선언되지 않은 리스트 참조

문제의 입력에 따라 탐색을 원하는 리스트에 값이 하나도 들어가지 않을 수 있고, 특정 분기문 내에서 선언한 값들이 바깥에서 참조된다면 조건이 다를 경우 선언되지 않은 메모리 공간을 참조할 수도 있다.

처음 짠 코드는 런타임 에러를 해결한다고 해도 통과할 수 없는 틀린 풀이이기 때문에 다른 블로거의 글을 참고하여 다시 작성했다.

작성하는 내내 분명 같은 문제를 읽고 조건에 맞게 구현을 했음에도 변수의 쓰임새나 특정 값을 구해내는 알고리즘의 설계가 효율적인 면에서 많이 차이 나는 걸 느끼고 감탄했다.

마지막으로 풀이에 대해 간단히 소개하면, 고장나지 않은 버튼으로 만들 수 있는 경우의 수는 이동하려는 채널이 500,000 까지이기 때문에 최대 10⁶ 이며 재귀로 구현할 경우 6번의 낮은 recursion depth 로 가능하다. 브루트 포스 문제인 만큼 모든 경우의 수를 탐색해도 시간초과가 나지 않을 2초의 시간제한이 주어져 여유있다. 보통 1초에 10⁸ 을 초과할 경우 시간초과가 난다고 한다.

참고

• [백준알고리즘] 1107번: 리모컨 -Python - 공부노트