[백준 2096] 내려가기

 

문제

---

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

2096번: 내려가기

 

 

나의 풀이

---

DP를 사용하는 문제이다. 메모리 제한이 아주 극심해서 여기에 신경쓰면서 코드를 구현해야 한다. 2차원 리스트로 DP를 구현하면 메모리 초과가 발생하므로 각각의 변수에 저장하도록 한다.

 

코드

---

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

import sys
input = sys.stdin.readline

N = int(input())
dp = [list(map(int, input().split())) for _ in range(N)]

lmax, cmax, rmax = dp[0][0], dp[0][1], dp[0][2]
lmin, cmin, rmin = dp[0][0], dp[0][1], dp[0][2]

for i in range(1, N):
    lmax, cmax, rmax = max(lmax, cmax) + dp[i][0], max(lmax, cmax, rmax) + dp[i][1], max(cmax, rmax) + dp[i][2]
    lmin, cmin, rmin = min(lmin, cmin) + dp[i][0], min(lmin, cmin, rmin) + dp[i][1], min(cmin, rmin) + dp[i][2]

print(max(lmax, cmax, rmax), min(lmin, cmin, rmin))