글 읽기 - 무슨 런타임 에러가 뜨는 걸까요?

wow056 5년 전 0

메모이제이션 방식으로 프로그램을 짰습니다.

하지만 숫자가 어느 정도 커지면 런타임 에러를 내뿜으며 프로그램이 죽습니다.

그런데 엄청난 양의 재귀함수가 호출되서 그런지 출력하는 예외의 양이 너무 많아 확인이 불가능합니다.

대체 무엇 때문에 런타임 에러가 뜨는 걸까요?

dictionary = {}


def calculate(n):
    if n == 1:
        return 0
    else:
        global dictionary
        try:
            return dictionary[n]
        except KeyError:
            templist = []
            if n % 3 == 0:
                templist.append(calculate(n // 3) + 1)
            if n % 2 == 0:
                templist.append(calculate(n // 2) + 1)
            templist.append(calculate(n - 1) + 1)
            dictionary[n] = min(templist)
            return dictionary[n]
            

X = int(input())
print(calculate(X))

djm03178 5년 전 1

이 문제는 재귀 top-down dp로 풀 시 필연적으로 깊이가 최대 약 50만에 육박하게 됩니다.

파이썬의 기본 재귀 한계는 약 1000회이고, setrecursionlimit을 하더라도 여기까지 늘리지는 못 하는 것으로 알고 있습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

무슨 런타임 에러가 뜨는 걸까요?

wow056 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말