[Python] 2096 내려가기

1. 문제 📚

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

2096번: 내려가기

2. 입출력 예 📋

3. 알고리즘 ✅

아무리 생각해도 로직은 맞는 거 같은데 자꾸 메모리 초과가 떠서 질문게시판을 참고했다

알고보니 입력부분 때문에 문제였다 ㅡ3ㅡ

이 글(https://www.acmicpc.net/board/view/82973)을 보고 그 부분만 수정하니 정답처리가 됐다

입력값은 크고, 현재 min과 max값은 그 전 위치가 영향을 주므로 dp라고 생각되어서 dp 방식으로 접근했다. 

min_dp와 max_dp 를 각각 두어 그 자리에 올 수 있는 max, min값 + 현재위치 값을 넣어주었다

중간에 temp 배열을 넣은 이유는 하나하나 실행할 때마다 dp의 max값 or min값을 찾기 때문에 영향을 주지 않기 위해 두었다

마지막에 min_dp = temp로 두어 값을 교체하는 방식으로 진행하였다! 

4. 소스코드 💻

"""
3
1 2 3
4 5 6
4 9 0
"""
import sys

input = sys.stdin.readline

N = int(input().strip())

max_dp = [0 for _ in range(3)]
min_dp = [0 for _ in range(3)]

for i in range(N):
    first, second, third = map(int, input().strip().split())

    temp = [0 for _ in range(3)]
    temp[0] = first + min(min_dp[0], min_dp[1])
    temp[1] = second + min(min_dp[0], min_dp[1], min_dp[2])
    temp[2] = third + min(min_dp[1], min_dp[2])

    min_dp = temp[:]

    temp = [0 for _ in range(3)]

    temp[0] = first + max(max_dp[0], max_dp[1])
    temp[1] = second + max(max_dp[0], max_dp[1], max_dp[2])
    temp[2] = third + max(max_dp[1], max_dp[2])

    max_dp = temp[:]

print(max(max_dp), min(min_dp), end = ' ')

 

끝!