728x90

문제 189. (2022-02-19)

 

Baekjoon 1932. 정수 삼각형

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

 


입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

 


출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

 


입력 예시

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

 


출력 예시

30

 


❧ 정답

from sys import stdin
n = int(stdin.readline())
dp = [0, ] # dp table
triangle = [0, ] # 입력값 저장
for i in range(1, n + 1):
line = list(map(int, stdin.readline().split()))
triangle.append(line)
dp.append([0] * i)
dp[1] = [triangle[1][0]] # [0, [7], [10, 15], ...]
for i in range(2, n + 1):
for j in range(len(triangle[i])): # len(triagle[3]) : 3, 8 1 0
left, right = 0, 0
if j > 0:
left = dp[i - 1][j - 1] # 위층의 좌측 원소
if j < i - 1:
right = dp[i - 1][j] # 위층의 우측 원소
dp[i][j] = max(left, right) + triangle[i][j]
print(max(dp[n]))

🔎IDEA) DP - 이전 층의 최댓값을 더해주며 맨 위층에서부터 맨 아래층까지 순차적으로 내려온다.

[Line 6 - 9]
👉 triangle에 입력값을 받아서 리스트를 만들고 dp에 한줄 개수대로 dp 테이블을 만든다.

[Line 12 - 19]
👉 입력받은 정수 삼각형의 맨 위 노드에서 맨 아래 노드로 값을 순회하며 윗 줄에서 더 높은 값을 더하면서 삼각형을 내려온다.
👉 left 에는 위층의 좌측 원소 값을 넣고 right에는 위층의 우측 원소 값을 넣는다.
👉 이후 leftright의 값을 비교하여 두 값 중 더 큰 값과 현재 노드의 값을 더해주며 dp 테이블에 값을 넣어준다.

728x90