[백준] 2096(파이썬) - 내려가기

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

2096번: 내려가기

• 이 문제는 메모리를 보면 4MB....
• DP를 사용해도 메모이제이션을 쓰면 안 되고 현재의 상태만 배열에 저장해 두고 값을 비교해서 갱신해 내 가는 방식으로 구현해야 했다.
• PYPY로 풀었을 때는 입력값을 일단 받아서 배열에 넣고 그 배열 값의 첫 번째 값을 변수에 담은 뒤, 변수를 갱신해 나가는 방법을 사용했다. PYPY3에서 N이 100000이라고 가정했을 때 100000번을 입력받는 것 또한 메모리 초과가 날거라 생각했지만 나지 않았다.
• Python3로 풀었을 때는 메모리 초과가 발생했고 그 해결방법은 각각 비교해서 갱신할 때, 입력값을 각각 따로 받아서 구현하는 것이다.
• 위에는 PYPY로 풀었을 때, 아래는 Python3로 풀었을 때 코드이다.

import sys
input = sys.stdin.readline

n = int(input())

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

# 시작 
max1,max2,max3 = data[0][0],data[0][1],data[0][2]
min1,min2,min3 = data[0][0],data[0][1],data[0][2]

for i in range(1,n):
    max1,max2,max3 = max(max1,max2) + data[i][0], max(max1,max2,max3) + data[i][1], max(max2,max3) + data[i][2]
    min1, min2, min3 = min(min1, min2) + data[i][0], min(min1, min2, min3) + data[i][1], min(min2, min3) + data[i][2]

print(max(max1,max2,max3),min(min1,min2,min3))
#############################################################################################
import sys
n = int(input())

# 메모리 제한으로 전 시점과 현 시점의 최적해만 가지고 다닐 DP 선언
a, b, c = map(int, sys.stdin.readline().split())
max_dp = [a,b,c]
min_dp = [a,b,c]


# 현재 계단 이전에 선택할 수 있는 최적해 + 현재 계단의 값
for i in range(1, n):
    a, b, c = map(int, sys.stdin.readline().split())
    for j in range(3):
        if j == 0:
            max_first =  max(max_dp[j], max_dp[j+1]) + a
            min_first =  min(min_dp[j], min_dp[j+1]) + a
        if j == 1:
            max_second = max(max_dp[j-1], max_dp[j], max_dp[j+1]) + b
            min_second = min(min_dp[j-1], min_dp[j], min_dp[j+1]) + b
        if j == 2:
            max_third = max(max_dp[j-1], max_dp[j]) + c
            min_third = min(min_dp[j-1], min_dp[j]) + c
    max_dp = [max_first, max_second, max_third]
    min_dp = [min_first, min_second, min_third]
    
print(max(max_dp), min(min_dp))