[Python] 백준2096 내려가기

23 May 2023 in Study on Algorithm

백준2096 내려가기 링크

문제

예제 입력

---

코드

import sys

n = int(input())

mindp = [0,0,0]
mintmp = [0,0,0]
maxdp = [0,0,0]
maxtmp = [0,0,0]

for _ in range(n):
    a, b, c = map(int, sys.stdin.readline().split())
    for i in range(3):
        if i == 0:
            mintmp[0] = a + min(mindp[0], mindp[1])
            maxtmp[0] = a + max(maxdp[0], maxdp[1])
        elif i == 1:
            mintmp[1] = b + min(mindp[0], mindp[1], mindp[2])
            maxtmp[1] = b + max(maxdp[0], maxdp[1], maxdp[2])
        else :
            mintmp[2] = c + min(mindp[1], mindp[2])
            maxtmp[2] = c + max(maxdp[1], maxdp[2])
            
    for i in range(3):
        mindp[i] = mintmp[i]
        maxdp[i] = maxtmp[i]

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

설명

파이썬을 통해서 사용자로부터 입력받아 dp알고리즘을 사용하여 내려가기를 구현했는데 배열을 선언할 수 있는 메모리가 부족하기 때문에 tmp로 min,max를 계산하여 임시저장하는 것으로 보완할수 있습니다.

---

결과