글 읽기 - 파이썬 런타임에러

mygm1302 5년 전 0

포도주의 개수가 n개일때 마실수 있는 최대량을 f(n)이라 하고,

n번째 포도주의 양을 an이라고 할때

f(n)=max(f(n-1),f(n-2)+an,(fn-3)+an+a(n-1))

임을 이용하여 풀었습니다.

반복문을 이용해 bottom-up으로 풀었을때는 런타임에러가 발생하지 않았는데,

재귀를 이용해 top-down으로 풀었을때는 런타임에러가 발생했습니다.

sys모듈을 임포트해 재귀 깊이를 인위적으로 늘려보아도 시간 초과가 발생합니다.

단순히 함수 호출에 의한 오버헤드때문인가요?

아니면 제가 놓친 부분이 있는건가요?

import sys;
sys.setrecursionlimit(10**6);
n=int(input());
d=[-1]*n;
wine=[-1]*n;
for i in range(n):
    wine[i]=int(input());
d[0]=wine[0]
if(n>=2):d[1]=wine[1]+wine[0]
if(n>=3):d[2]=max(wine[0]+wine[1],wine[1]+wine[2],wine[0]+wine[2]);
def bestSum(N):
    if(d[N]!=-1):return d[N];
    result=max(bestSum(N-1),bestSum(N-2)+wine[N],bestSum(N-3)+wine[N]+wine[N-1]);
    d[N]=result;
    return result
if(n<=3):print(d[n-1]);
else:print(bestSum(n-1))

jh05013 5년 전 1

놀랍게도 그냥 Python3로 제출하면 잘 돌아갑니다. Pypy3가 불안정하긴 한데 이건 너무 이상하군요.

@startlink

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

문제

문제

출처

ICPC

파이썬 런타임에러

mygm1302 5년 전 0

jh05013 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말