728x90
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
❧ 정답
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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
에는 위층의 우측 원소 값을 넣는다.
👉 이후 left
와 right
의 값을 비교하여 두 값 중 더 큰 값과 현재 노드의 값을 더해주며 dp 테이블에 값을 넣어준다.
728x90
'📊 Algorithm > Algorithm PS' 카테고리의 다른 글
[알고리즘 일기 - 파이썬] 191. 돌 게임 (0) | 2022.02.28 |
---|---|
[알고리즘 일기 - 파이썬] 190. 경쟁적 전염 (0) | 2022.02.28 |
[알고리즘 일기 - 파이썬] 188. 2xn 타일링 (0) | 2022.02.28 |
[알고리즘 일기 - 파이썬] 187. 휴게소 세우기 (0) | 2022.02.28 |
[알고리즘 일기 - 파이썬] 186. 퇴사 (0) | 2022.02.28 |