글 읽기 - 두 코드의 시간 차이가 왜 이리 많이 나는건가요?

clssl15 2년 전 0

제가 짠 코드는 1148ms이고 어떤 사람이 짠 코드는 84ms입니다.

비록, 서버차이 sys.stdin.readline 의 차이가 있더라도 코드가 굉장히 유사한데 왜 이렇게 차이가 나는건가요?

#내가 짠 코드(1148ms)
dic={(0,0,0):1}
def w(a,b,c):
    if (a,b,c) in dic:
        return dic[(a,b,c)]
    if a<=0 or b<=0 or c<=0:
        return 1
    elif a>20 or b>20 or c>20:
        return w(20,20,20)
    elif a<b and b<c:
        dic[(a,b,c)]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)
        return dic[(a,b,c)]
    else:
        dic[(a,b,c)]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)
        return dic[(a,b,c)]

while 1:
    a,b,c=map(int,input().split())
    if a==-1 and b==-1 and c==-1:
        break
    else:
        print(f'w({a}, {b}, {c}) = {w(a,b,c)}')

#남이 짠 코드(84ms)
import sys

reg = [[[-1] * 21 for _ in range(21)] for _ in range(21)]

def w(a, b, c):
    global reg
    
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    if a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)
    if reg[a][b][c] != -1:
        return reg[a][b][c]
    if a < b < c:
        reg[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)
        return reg[a][b][c]

    reg[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1)
    return reg[a][b][c]

while True:
    a, b, c = map(int, sys.stdin.readline().split())
    if a == b == c == -1:
        break

    print("w(%d, %d, %d) = %d" % (a, b, c, w(a, b, c)))

djm03178 2년 전 2

dict는 평균 시간 복잡도만 상수일 뿐 실제로는 매우 매우 느린 자료구조입니다. 리스트와는 비교할 수 없습니다.

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

문제

문제

출처

ICPC

두 코드의 시간 차이가 왜 이리 많이 나는건가요?

clssl15 2년 전 0

djm03178 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말