글 읽기 - 시간초과..

mygm1302 5년 전 0

pypy3으로 돌릴때 5%쯤에서 시간초과가 뜹니다.

코드의 시간복잡도가 O(n^3)인데, 찾아보니 크누스 최적화라는 기법을 적용하면 O(n^2)이 되면서 통과가 된다고 들었습니다.

제 부족한 안목으로 보았을때, 조금 특수한 상황에서 쓸 수 있는 해법으로 보여 상담드립니다.

현재 DP를 처음배우는 입장에서 단계별로 풀어보기 도중 이문제를 마주쳤는데, 해당 최적화 기법을 공부하는게 맞을까요, 아니면 넘어가고 나중에 돌아와서 하는게 나을까요?

그리고 시간초과가 떠서 제 코드에 오류가 있는지 판단이 되지를 않는데, 수정할만한 것들이 있다면 알려주신다면 감사하겠습니다.

n=int(input());
paper=[];
psum=[0];
d=[];
def minCost(first,last):
    temp=10000000000
    if(d[first][last]!=-1):return d[first][last]
    if(last==first):return 0
    nowsum=psum[last]-psum[first-1]
    for i in range(first,last):
        temp=min(temp,nowsum+minCost(first,i)+minCost(i+1,last));
    d[first][last]=temp;
    return temp;
for i in range(n):
    m=int(input());
    paper=list(map(int,input().split()));
    psum=[0]*(1+m)
    sum=0;
    for i in range(m):
        sum+=paper[i];
        psum[i]=sum
    psum[-1]=0;
    d=[-1]*m;
    for i in range(m):
        d[i]=[-1]*m;
    print(minCost(0,m-1));

jh05013 5년 전 0

범위가 작아서 O(n^3)에도 풀 수 있습니다.

이것 때문인지 확실하진 않으나, 파이썬의 재귀는 꽤 무겁습니다. 재귀 없는 DP를 짜 보세요.

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

문제

문제

출처

ICPC

시간초과..

mygm1302 5년 전 0

jh05013 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말