[Python] 백준 2096번 : 내려가기

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

2096번: 내려가기

---

💡 문제 풀이

DP 문제이다.

 

메모리의 크기가 매우 작으므로 입력 값을 받는 동시에 최댓값과 최솟값을 따져준다.

✔️ 느낀 점

단순히 2차원 배열로 구현할 수 있다. 크게 어렵진 않지만 메모리 크기 때문에 조금 생각을 바꿀 필요가 있는 문제이다.

조금 바꾸는게 너무 어려웠다..

💻 코드

import sys

input = sys.stdin.readline
n = int(input())

DP_max = [0] * 3
DP_min = [0] * 3

max_ = [0] * 3
min_ = [0] * 3

for x in range(n):
    a, b, c = map(int, input().split())
    for y in range(3):
        if y == 0:
            max_[y] = a + max(DP_max[y], DP_max[y + 1])
            min_[y] = a + min(DP_min[y], DP_min[y + 1])
        if y == 1:
            max_[y] = b + max(DP_max[y - 1], DP_max[y], DP_max[y + 1])
            min_[y] = b + min(DP_min[y - 1], DP_min[y], DP_min[y + 1])
        if y == 2:
            max_[y] = c + max(DP_max[y], DP_max[y - 1])
            min_[y] = c + min(DP_min[y], DP_min[y - 1])

    for y in range(3):
        DP_max[y] = max_[y]
        DP_min[y] = min_[y]

print(max(DP_max), min(DP_min))