백준 2096번 내려가기

https://www.acmicpc.net/problem/2096

2096번: 내려가기

기본적인 DP문제이나 메모리 제한이 4메가 밖에 되지 않음으로 무작정 이전의 연산 결과를 저장할 리스트를 만들면 메모리 초과가 나게된다.

이점을 주의를 해서 코딩을 해주면 된다.

 

import sys
input = sys.stdin.readline

N = int(input())

max_matrix = [0,0,0]
min_matrix = [0,0,0]

for _ in range(N):
    a, b, c = map(int,input().split())

    new_a = max(a + max_matrix[0], a + max_matrix[1])
    new_b = max(b + max_matrix[0], b + max_matrix[1], b + max_matrix[2])
    new_c = max(c + max_matrix[1], c + max_matrix[2])

    max_matrix = [new_a,new_b,new_c]

    new_a = min(a + min_matrix[0], a + min_matrix[1])
    new_b = min(b + min_matrix[0], b + min_matrix[1], b + min_matrix[2])
    new_c = min(c + min_matrix[1], c + min_matrix[2])

    min_matrix = [new_a,new_b,new_c]

print(max(max_matrix))
print(min(min_matrix))