python 백준 2096 내려가기

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

• dp 활용
  • 해당 줄을 선택시의 최대,최소값을 dp에 저장
• 메모리 문제
  • 바로 전의 값만 필요하므로 dp에 현재값,이전값만 저장공간 배치
  • 2로 나눈 나머지연산을 통해 이전값, 현재값 저장

import sys
N = int(sys.stdin.readline())
dp = [[[0,0] for _ in range(3)] for __ in range(2)]

for i in range(N):
    temp = list(map(int,sys.stdin.readline().split()))
    ii = i % 2
    for j in range(3):
        if j == 0:
            dp[ii][j][0] = max(dp[1-ii][j][0],dp[1-ii][j+1][0])+temp[j]
            dp[ii][j][1] = min(dp[1-ii][j][1],dp[1-ii][j+1][1])+temp[j]
        elif j == 1:
            dp[ii][j][0] = max(dp[1-ii][j][0],dp[1-ii][j-1][0],dp[1-ii][j+1][0])+temp[j]
            dp[ii][j][1] = min(dp[1-ii][j][1],dp[1-ii][j-1][1],dp[1-ii][j+1][1])+temp[j]
        else:
            dp[ii][j][0] = max(dp[1-ii][j][0],dp[1-ii][j-1][0])+temp[j]
            dp[ii][j][1] = min(dp[1-ii][j][1],dp[1-ii][j-1][1])+temp[j]

max_point,min_point = 0,1000000
for target in dp[1-N%2]:
    if target[0] > max_point:
        max_point = target[0]
    if target[1] < min_point:
        min_point = target[1]
print(max_point,min_point)