[Python] 1932번 정수 삼각형

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

1932번: 정수 삼각형

---

 

22/09/18

 

 

전형적인 DP문제로, 이것과 비슷하게 어떤 행렬을 주고 내려오면서 DP를 계속 갱신하는 유형의 문제로는 스티커, 내려가기 2 등이 있다. 

---

 

문제 접근 방식:

 

 

내려가면서 DP리스트를 갱신해주는데, DP[i]는 n번째 줄(n개의 숫자가 있음)에서 i번째 숫자에 도착했을 때, 경로의 최댓값이다.

 

나는 2차원 배열을 선언하는 대신에 DP리스트를 매 반복문마다 갱신해줌으로써 문제를 해결하였다.

 

아래로 떨어질 때, DP[0]은 제일 왼쪽에 있는 원소에서 내려가야만 도달할 수 있고, 중간 것들(DP[i])는 이전 줄의 i-1번째 원소와 i번째 원소에서 내려갈 수 있으므로, 둘 중에서 큰 값을 선택한다.

 

이후 DP[n]은 이전 줄에서 제일 오른쪽에 있는 원소에서 내려가야만 도달할 수 있으므로, 이를 고려하여 구현하면 된다.

 

비슷한 유형의 문제를 위에서 언급했으니, 만약 내려가기 2를 풀어본다면, 이 문제를 쉽게 풀 수 있을 것이라 생각한다.

---

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

# 1932번 정수 삼각형
# DP
import sys
input = sys.stdin.readline

N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]

line = matrix[0]
for i in range(1, N):
	line_2 = [line[0]+matrix[i][0]]
	for j in range(1, len(line)):
		line_2.append(max(line[j-1], line[j])+matrix[i][j])
	line_2.append(line[len(line)-1]+matrix[i][-1])
	line = line_2
print(max(line))