풀이

1. 평범한 DP문제처럼 보이지만 메모리 제한에 주의할 것
2. 일반적으로 메모리 사용량 기준은 MB 단위로 제시됨
   • 코테는 대부분 리스트 사용하는 데 정수형 int 타입 기준 아래와 같음
     • int a[1000]=4KB (int자료형은 4byte)
     • int a[1000000]=4MB ($10^6$)
     • int a[2000][2000]=16MB ($4\times10^6$)
3. 4MB 기준으로 배열을 작성해야하기 때문에 문제의 N줄 조건을 유의할 것 → 100,000이기 때문에 배열 생성에 주의해야함.
   

위에 색칠한 것 과 같이
[i][0]=max([i-1][0],[i-1][1])
[i][1]=max([i-1])
[i][2]=max([i-1][1],[i-1][2])

로 다음 줄의 값이 정해진다. 근데 굳이 DP를 처음 주어진 숫자 배열만큼 만들 필요는 없다. 그냥 그때그때 입력받아서 DP를 정의해주면 메모리 걱정이 끝이다.

DP를 만약에 주어진 숫자배열과 똑같이 만들어서 최대와 최소를 구하게 되면 $1,000,000\times3$ 이 2개 더 만들어지기 때문에 메모리 오류가 날 수 밖에 없다.

그냥 DP를 1차원 배열로 선언하고 아예 새로운 값을 할당하면 메모리를 아낄 수 있다. 핵심은 "이전 줄 정보만 기억하면 되니까 전체 배열을 만들 필요 없다"는 것이고

이를 슬라이싱 윈도우라고 한다. 점화식을 세웠을때 바로 직전의 값만 알아도 현재의 값을 구할 수 있을 때 사용하면 메모리를 아낄 수 있다.

# 2096 내려가기
import sys
input=sys.stdin.readline
N=int(input())
first_row=list(map(int,input().split()))

maxdp=first_row # max값 갱신할 DP 첫번째 줄은 그냥 값 넣기
mindp=first_row # min값 갱신할 DP 첫번째 줄은 그냥 값 넣기
for _ in range(N-1):
    new_line=list(map(int,input().split()))
    # 입력받은 값에 이전 점화식 그대로 적용해서 maxdp 자체를 다시 초기화
    maxdp=[new_line[0]+max(maxdp[0],maxdp[1]),new_line[1]+max(maxdp),new_line[2]+max(maxdp[1],maxdp[2])]
    # 입력받은 값에 이전 점화식 그대로 적용해서 mindp 자체를 다시 초기화
    mindp=[new_line[0]+min(mindp[0],mindp[1]),new_line[1]+min(mindp),new_line[2]+min(mindp[1],mindp[2])]

print(max(maxdp),min(mindp))