[Python] 15645번 내려가기 2

15645번: 내려가기 2 (acmicpc.net)

15645번: 내려가기 2

---

 

22/09/07

 

 

이전에 북마크 해놓았던 문제 중 하나로, 무난하게 풀 수 있었던 dp문제였다.

 

이전에 비슷한 문제를 풀어서 쉽게 풀 수 있었다.

---

 

문제 접근 방식:

 

 

사실 dp류의 문제는 아이디어만 알면 구현하는 것 자체는 그렇게 어렵지 않은 문제가 꽤 많다.

 

이것도 그러한데, 아이디어는 다음과 같다.

 

각각의 dp리스트를 정의해주었다. 총 6개가 존재하는데, 예를 들면 다음과 같다.

 

first_line_min[N]은 내가 N번째 가로줄까지 내려갔을 때, 첫 번째 줄로 도착했을 경우의 최솟값을 모아놓은 리스트이다.

이후 줄은 2개가 있고, 최대 최소를 구해야 하므로 마찬가지 방법으로 5개의 리스트를 모두 위의 정의와 비슷하게 만들어준다.

 

이제 min값을 구하기 위해 각각의 first, second, third line min 리스트들을 채워주는 작업을 진행한다.

 

예를 들어 first_line의 경우, 그 이전에 첫번째와 두 번째에 도착해야지만 갈 수 있으므로, first_line_min[N] = min(first_line_min[N-1], second_line_min[N-1]) + matrix[N][0] 이라는 식이 성립된다.(입력받은 숫자들을 matrix라고 한다면)

 

마찬가지로, 두 번째, 세 번째도 이와 비슷한 방식으로 구할 수 있다.

 

최종 min값은 first, second, third_line_min 리스트의 마지막 값들 중에서 가장 작은 값을 고르면 된다.

 

비슷한 방식으로 max값을 구현할 수 있으며, 이는 이 글을 읽는 사람들의 몫으로 남겨놓겠다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 15645번 내려가기 2
# DP
import sys
input = sys.stdin.readline

first_line_min = []  # N반째 줄까지 갔을 때, 첫번째 원소에 도착했을 경우에서의 최솟값
first_line_max = []
second_line_min = []
second_line_max = []
third_line_min = []
third_line_max = []

N = int(input())
dp = []
for _ in range(N):
    dp.append(tuple(map(int, input().split())))
# min값을 구하는 과정
first_line_min.append(dp[0][0])
second_line_min.append(dp[0][1])
third_line_min.append(dp[0][2])
for i in range(1, N):
    first_line_min.append(min(first_line_min[i-1], second_line_min[i-1]) + dp[i][0])
    second_line_min.append(min(first_line_min[i-1], second_line_min[i-1], third_line_min[i-1]) + dp[i][1])
    third_line_min.append(min(second_line_min[i-1], third_line_min[i-1]) + dp[i][2])
total_min = min(first_line_min[N-1], second_line_min[N-1], third_line_min[N-1])
# max값을 구하는 과정
first_line_max.append(dp[0][0])
second_line_max.append(dp[0][1])
third_line_max.append(dp[0][2])
for i in range(1, N):
    first_line_max.append(max(first_line_max[i-1], second_line_max[i-1]) + dp[i][0])
    second_line_max.append(max(first_line_max[i-1], second_line_max[i-1], third_line_max[-1]) + dp[i][1])
    third_line_max.append(max(second_line_max[i-1], third_line_max[i-1]) + dp[i][2])
total_max = max(first_line_max[N-1], second_line_max[N-1], third_line_max[N-1])

print(total_max, total_min)