2096 - 내려가기 / gold 5 / DP

"""
2096 - 내려가기 / gold 5 / DP
"""
import copy

n = int(input())
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

dp_min = copy.deepcopy(graph)
dp_max = copy.deepcopy(graph)
for i in range(1, n):
    for j in range(3):
        if j == 0:
            dp_min[i][0] = dp_min[i][0] + min(dp_min[i - 1][0], dp_min[i - 1][1])
            dp_max[i][0] = dp_max[i][0] + max(dp_max[i - 1][0], dp_max[i - 1][1])

        elif j == 1:
            dp_min[i][1] = dp_min[i][1] + min(
                dp_min[i - 1][0], dp_min[i - 1][1], dp_min[i - 1][2]
            )
            dp_max[i][1] = dp_max[i][1] + max(
                dp_max[i - 1][0], dp_max[i - 1][1], dp_max[i - 1][2]
            )
        elif j == 2:
            dp_min[i][2] = dp_min[i][2] + min(dp_min[i - 1][1], dp_min[i - 1][2])
            dp_max[i][2] = dp_max[i][2] + max(dp_max[i - 1][1], dp_max[i - 1][2])

print(max(dp_max[n - 1]), min(dp_min[n - 1]))

- copy 모듈 사용 / 메모리 초과

"""
2096 - 내려가기 / gold 5 / DP
"""
n = int(input())
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

dp_min = [graph[0][0], graph[0][1], graph[0][2]]
temp_min = [graph[0][0], graph[0][1], graph[0][2]]
dp_max = [graph[0][0], graph[0][1], graph[0][2]]
temp_max = [graph[0][0], graph[0][1], graph[0][2]]
for i in range(1, n):
    for j in range(3):
        if j == 0:
            dp_min[0] = graph[i][0] + min(temp_min[0], temp_min[1])
            dp_max[0] = graph[i][0] + max(temp_max[0], temp_max[1])

        elif j == 1:
            dp_min[1] = graph[i][1] + min(temp_min[0], temp_min[1], temp_min[2])
            dp_max[1] = graph[i][1] + max(temp_max[0], temp_max[1], temp_max[2])
        elif j == 2:
            dp_min[2] = graph[i][2] + min(temp_min[1], temp_min[2])
            dp_max[2] = graph[i][2] + max(temp_max[1], temp_max[2])
    temp_min[0], temp_min[1], temp_min[2] = dp_min[0], dp_min[1], dp_min[2]
    temp_max[0], temp_max[1], temp_max[2] = dp_max[0], dp_max[1], dp_max[2]

print(max(dp_max), min(dp_min))

- 리스트들 너무 많이 사용했기에, graph 리스트만 남기고 했지만, 또 메모리 초과

 

"""
2096 - 내려가기 / gold 5 / DP
"""
n = int(input())

dp_min = [0, 0, 0]
dp_max = [0, 0, 0]
temp_min = [0, 0, 0]
temp_max = [0, 0, 0]

for i in range(n):
    first, second, third = map(int, input().split())

    dp_min[0] = first + min(temp_min[0], temp_min[1])
    dp_min[1] = second + min(temp_min[0], temp_min[1], temp_min[2])
    dp_min[2] = third + min(temp_min[1], temp_min[2])

    dp_max[0] = first + max(temp_max[0], temp_max[1])
    dp_max[1] = second + max(temp_max[0], temp_max[1], temp_max[2])
    dp_max[2] = third + max(temp_max[1], temp_max[2])

    temp_min[0], temp_min[1], temp_min[2] = dp_min[0], dp_min[1], dp_min[2]
    temp_max[0], temp_max[1], temp_max[2] = dp_max[0], dp_max[1], dp_max[2]


print(max(dp_max), min(dp_min))

입력받은 것을 graph 리스트에 저장하지 않고,

입력할 시 바로 dp_min, dp_max 인덱스 값들을 바꿔주기

 

dp 알고리즘 + 메모리 관리 문제였다~