[백준2096] / 내려가기 - DP

 

백준2096

 

푼 날짜 : 2024.10.12

푼 문제 : [2096] / 내려가기

사용한 언어 : python

알고리즘 : DP

 

 

접근 방식 :

처음에 일반적인 DP로 풀다가 메모리 초과가 났다.

생각해보면 DP는 현재값 계산을 위해 이전 값을 활용하기 때문에 다음 계산 전 현재 값을 이전 값으로 덮어씌웠다.

# 덮어쓰기
dp[0][0] = dp[1][0]
dp[0][1] = dp[1][1]
dp[0][2] = dp[1][2]

dp2[0][0] = dp2[1][0]
dp2[0][1] = dp2[1][1]
dp2[0][2] = dp2[1][2]

 

이렇게 하면 모든 DP 배열을 채우지 않고 단순하게 계산할 수 있다.

 

 

코드 :

import sys

N = int(sys.stdin.readline())

dp = [[0, 0, 0], [0, 0, 0]]
dp2 = [[0, 0, 0], [0, 0, 0]]

a, b, c = map(int, sys.stdin.readline().split())

dp[0][0] = dp2[0][0] = a
dp[0][1] = dp2[0][1] = b
dp[0][2] = dp2[0][2] = c

for _ in range(1, N):
    a, b, c = map(int, sys.stdin.readline().split())

    dp[1][0] = max(dp[0][0], dp[0][1]) + a
    dp[1][1] = max(max(dp[0][0], dp[0][1]), dp[0][2]) + b
    dp[1][2] = max(dp[0][1], dp[0][2]) + c

    dp2[1][0] = min(dp2[0][0], dp2[0][1]) + a
    dp2[1][1] = min(min(dp2[0][0], dp2[0][1]), dp2[0][2]) + b
    dp2[1][2] = min(dp2[0][1], dp2[0][2]) + c

	# 덮어쓰기
    dp[0][0] = dp[1][0]
    dp[0][1] = dp[1][1]
    dp[0][2] = dp[1][2]

    dp2[0][0] = dp2[1][0]
    dp2[0][1] = dp2[1][1]
    dp2[0][2] = dp2[1][2]

print(max(dp[0]), min(dp2[0]))

 

 

뿌듯 !