[알고리즘/파이썬] 백준 2096 - 내려가기

문제

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

2096번: 내려가기

 

풀이

RGB거리랑 비슷하다고 생각해서 그렇게 풀었더니 초과가 나왔다 ㅎㅎ  메모리 제한이 있어서 처음 입력값 자체를 하나의 거대한 arr로 저장해두는 것 자체가 안 되는 것 같았다. 그래서 입력받을 때마다 바로바로 맥스,민 값을 저장해둬야 겠다고 생각하고 코드를 변경했다.

일반적인 디피 문제라서 어렵진 않지만 메모리를 어떻게 적게 쓸 것인가를 고민했던 문제!

 

코드

from sys import stdin

N = int(input())

# DP초기값 설정
arr = list(map(int, stdin.readline().split()))
max_arr = arr
min_arr = arr

for _ in range(N - 1):
    arr = list(map(int, stdin.readline().split()))
    
    max_arr = [arr[0] + max(max_arr[0], max_arr[1]), arr[1] + max(max_arr), arr[2] + max(max_arr[1], max_arr[2])]
    min_arr = [arr[0] + min(min_arr[0], min_arr[1]), arr[1] + min(min_arr), arr[2] + min(min_arr[1], min_arr[2])]

print(max(max_arr), min(min_arr))