[BOJ] 2096. 내려가기

www.acmicpc.net/problem/2096

2096번: 내려가기

 

문제: 주어진 배열에서 인접한 부분으로 위에서 부터 내려가며 숫자를 더할 때, 최소 값과 최대 값을 구하여라

 

문제 이해하기!!

DP문제로, 앞에서 더한 인접한 부분 것들에 최대 값과 최소 값을 구해서 더해가며 밑으로 내려가면 되는 문제입니다.

하지만 이 문제만 나온다면 골드문제가 아니라 실버 1~2 정도 문제겠죠?

이 문제는 DP로 푸는 방법만 구하는게 아니라 실제로 사용되는 메모리의 양도 중요했던 문제입니다.

이 문제를 풀려면 입력받는 즉시 그 값을 사용해서 DP 계산을 해야합니다.

 

그래서 푼 방법은

1. 처음 입력받은 값들은 최소 DP와 최대 DP의 초기값이 됩니다.

2. 점차 1줄씩 내려가며 입력을 받고, DP 값을 비교 및 더합니다.

3. DP의 크기는 계속 커지는 것이 아니라 업데이트되는게 중요합니다.

4. 마지막으로 업데이트 된 최대 DP와 최소 DP의 최대, 최소값을 출력합니다.

 

코드:

from sys import stdin
input = stdin.readline

N = int(input())
max_dp = list(map(int, input().split()))
min_dp = max_dp[:]
for i in range(N-1):
    arr = list(map(int, input().split()))
    tmp1 = max_dp[:]
    tmp2 = min_dp[:]
    max_dp[0] = arr[0] + max(tmp1[0], tmp1[1])
    max_dp[1] = arr[1] + max(tmp1[0], tmp1[1], tmp1[2])
    max_dp[2] = arr[2] + max(tmp1[2], tmp1[1])
    min_dp[0] = arr[0] + min(tmp2[0], tmp2[1])
    min_dp[1] = arr[1] + min(tmp2[0], tmp2[1], tmp2[2])
    min_dp[2] = arr[2] + min(tmp2[2], tmp2[1])

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