[Python] 2096 - 내려가기

[Gold V] 내려가기 - 2096

[문제 링크](https://www.acmicpc.net/problem/2096)

🗝️알고리즘 분류

• 다이나믹 프로그래밍

---

💻문제 정의

3개의 숫자들 중 하나를 골라 아래로 내려간다. 내려가는 방향은 바로 아래의 수와 인접한 수로만 이동할 수 있다.

내려간 후, 합의 최대와 최솟값을 구하는 문제이다.

 

💡접근 및 설계

딱 보자마자 다이나믹 프로그래밍이 떠오를 것이다. 현재의 점에서 아래로 내려가는 경우를 저장하여 마지막 줄에서의 최솟값과 최댓값을 출력하도록 설계하였다.

 

✏️알고리즘 풀이

dp_min = [0, 0, 0]
dp_max = [0, 0, 0]

for i in range(N):
    lst = list(map(int, input().split()))
    dp_max = [lst[0] + max(dp_max[:2]), lst[1] + max(dp_max), lst[2] + max(dp_max[1:])]
    dp_min = [lst[0] + min(dp_min[:2]), lst[1] + min(dp_min), lst[2] + min(dp_min[1:])]

먼저 [0, 0, 0]에서 시작한다. 각 줄을 입력받을 때, 각 칸으로 내려올 경우 중 최대의 경우와 최소의 경우만을 생각하여 값을 저장한다.

 

# [1, 2, 3]
# [4, 5, 6] => [4 + max(1, 2), 5 + max(1, 2, 3), 6 + max(2, 3)]

# [6, 8, 9] # result

4로 내려갈 수 있는 경우는 1과 2에서 4로 갈 수 있다. 따라서 4의 자리에는 4+1과 4+2가 될 수 있고, 이때 각 합의 최대와 최소를 저장한다.

 

🗒️제출 코드

# 2096 내려가기

N = int(input())

dp_min = [0, 0, 0]
dp_max = [0, 0, 0]

for i in range(N):
    lst = list(map(int, input().split()))
    dp_max = [lst[0] + max(dp_max[:2]), lst[1] + max(dp_max), lst[2] + max(dp_max[1:])]
    dp_min = [lst[0] + min(dp_min[:2]), lst[1] + min(dp_min), lst[2] + min(dp_min[1:])]

print(max(dp_max), min(dp_min))

---

💭오늘의 회고

DP는 언제 풀어도 어렵고, 머리가 아프다.

특히 한 몇주 쉬고 다시 풀려고 하니 예전같지 않는 듯한 느낌이다.

 

열심히 합시다...!