[백준] 2096_내려가기 (dp 이용)

📕 문제

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

2096번: 내려가기

 

💡 풀이법

1. 최대값을 저장해줄 max_dp, 최소값을 저장해줄 min_dp를 만든다.

(이때, 일반적인 dp와 다르게 n개의 길이로 만들어주면 메모리 초과 에러가 난다..ㅜ)

2. 당장 왼쪽, 가운데, 오른쪽에서 어떤 값이 최대, 최소일지 알 수 없기 때문에 각 위치를 선택했을때의 최대, 최소값을 구해주어야 한다.

3. 처음에는 0행의 숫자들을 넣어준다.

4. N개의 행이 있기 때문에 for문을 N번 돌면서 입력을 받아준다. 입력값을 저장해서 리스트로 만드는 것도 에러가 발생하기 때문에 입력과 즉시 max_dp, min_dp의 값을 변경해준다.

5. 결국 최종 max_dp, min_dp에는 각 위치에서의 최대값과 최소값이 담기게 된다. 이 중 제일 큰값과 제일 작은 값을 출력한다.

import sys
input = sys.stdin.readline

N = int(input())
max_dp = [0, 0, 0]
min_dp = [0, 0, 0]
numbers = list(map(int, input().split()))
max_dp[0], max_dp[1], max_dp[2] = numbers[0], numbers[1], numbers[2]
min_dp[0], min_dp[1], min_dp[2] = numbers[0], numbers[1], numbers[2]
for _ in range(1, N):
    numbers = list(map(int,input().split()))
    max_dp[0], max_dp[1], max_dp[2] = numbers[0] + max(max_dp[0], max_dp[1]), numbers[1] + max(max_dp[0], max_dp[1], max_dp[2]), numbers[2] + max(max_dp[1], max_dp[2])
    min_dp[0], min_dp[1], min_dp[2] = numbers[0] + min(min_dp[0], min_dp[1]), numbers[1] + min(min_dp[0], min_dp[1], min_dp[2]), numbers[2] + min(min_dp[1], min_dp[2])

print(max(max_dp), min(min_dp))