[백준(파이썬/Python)] 2096_내려가기

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

2096번: 내려가기

- 풀이 자체는 어렵지 않은데 문제의 메모리 제한이 상당히 타이트합니다.

 

- 현재 계단에서 점수의 최대, 최소는 그 전 계단까지의 최대 최소에만 영향을 받기 때문에 모든 계단의 점수값을 미리 배열로 만들어두면 메모리 초과가 발생합니다.

 

- 따라서, 계속해서 각 시점에서 인풋값을 읽고 최적해를 갱신해나가는 방향으로 문제를 풀어야합니다. 문제 풀이의 DP 로직은 첫번째, 두번째, 세번째 계단에 있을 때를 따로 생각해주면 어렵지 않은 것 같습니다.

 

[풀이]

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))