POLY를 python 3로 푸는데 시간초과가 뜹니다

  • liquoricej
    liquoricej

    POLY를 python 3로 푸는데 시간초과가 뜹니다. (pypy로는 됩니다만, 가능하면 py3로 풀고 싶습니다)
    테스트 케이스로 100을 100번 넣으니 약 10초가 걸리는데, 같이 푸는 사람이 같은 알고리즘을 써서 풀었을 때는 시간 초과가 안 났습니다.
    무슨 차이 때문에 이런 일이 생겼는지, 저로서는 리스트와 관련된 이슈가 있을 거라 있을 거라고 짐작할 뿐 원인을 짚지 못하고 있습니다.
    무엇 때문에 이런 차이가 생겼을런지요.

    아래 코드가 제 코드입니다.

    from sys import stdin
    C = int(input())
    ans = [0] * C
    size=[]
    for i in range(C):
        size.append(int(stdin.readline()))
    
    for ind in range(C):
        num = []    #num[a][b] : Polyomino of size a with head length b
        for n in range(size[ind]+1):
        #제 테스트 케이스는 이 for문에서 10초 중 8초가 걸립니다
            num.append([0] * (n+1))
            num[n][n] = 1
            for h in range(1,n):
                for k in range(1, n-h+1):
                    num[n][h] += (h + k -1) *  num[n-h][k]
        for i in range(1,n+1):
            ans[ind] = sum(num[n])
    
    for ind in range(C):
        print(ans[ind] % 10000000)

    아래는 시간 초과가 되지 않는 답입니다

    from sys import stdin
    build=[[0],[1]]
    def poly(n):
        for i in range(len(build),n+1):
            temp=[]
            for j in range(i-1):
                cand=0
                for k in range(i-j-1):                
                    cand+=((k+j+1)*build[i-j-1][k])%10000000
                temp.append(cand)
            temp.append(1)
            build.append(temp)
    
    for _ in range(int(stdin.readline())):
        n=int(stdin.readline())
        poly(n)
        print(sum(build[n])%10000000)

    6달 전
1개의 댓글이 있습니다.
  • liquoricej
    liquoricej

    해결했습니다. 제 코드는 그때그때 처음부터 num을 계산하는 반면, 같이 푼 사람의 코드는 num에 해당하는 변수를 미리 구해놓고 필요할 때 꺼내쓰는 방식을 썼더군요. 그래서 저도 미리 구해서 꺼내쓰는 방법으로 수정했습니다.


    6달 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.