글 읽기 - [Python] 메모리 초과 오류에서 못벗어나고 있습니다. 지적 부탁드립니다.

yordlejason 6년 전 0

이전에 제출했던 코드는 시간 초과로 실패,

마지막에 제출한 코드는 메모리 초과로 실패 처리를 받았습니다.

가능하시다면 제 코드상에서 문제가 될만한 부분을 지적해주시면

고쳐보겠습니다. 혹은, '알고리즘 자체가 비효율의 극치다!' 라고 생각하시면

솔직하게 따끔히 말씀해주셔도 정말 좋습니다 (추가로 참고하거나 알아야 할 지식을 알려주신다면 더더욱 따봉!...)

소중한 시간 할애해주셔서 감사합니다 :-)

답변 기다리겠습니다..!

from sys import stdin


def get_max_score(row1, row2, N):
    D = [[0, r1, r2] for r1, r2 in zip(row1, row2) for _ in range(N)]

    for i in range(1, N):
        D[i][0] = max(D[i-1][0], D[i-1][1], D[i-1][2])
        D[i][1] = max(D[i-1][0], D[i-1][2]) + row1[i]
        D[i][2] = max(D[i-1][0], D[i-1][1]) + row2[i]

    return max(D[N-1])

for _ in range(int(stdin.readline())):
    N = int(stdin.readline())
    r1 = list(map(lambda x: int(x), stdin.readline().split()))
    r2 = list(map(lambda x: int(x), stdin.readline().split()))
    print(get_max_score(r1, r2, N))

jh05013 6년 전 1

메모리와는 별개로, "lambda x: int(x)" 대신 그냥 "int"라고만 해도 됩니다.

D의 크기가 len(row1)*N인데 len(row1)은 N이므로 N^2이 됩니다. 이 정도의 배열로는 메모리 초과가 나고, 배열 없이 이중 for문을 돌려도 O(N^2)이므로 시간초과가 납니다.