🔗 Problem Link
❔Thinking
- 정수로 이루어진 삼각형에서, 위에서 큰 수를 선택해 더해 내려와 얻게되는 가장 큰 수를 반환한다.
- 왼쪽 대각선 아래, 오른쪽 대각선 아래의 수만 선택하여 더할 수 있다.
💻Solution
1. 위에서 내려오는 방법
import copy
n = int(input())
graph = [[]]
for i in range(n):
graph.append(list(map(int, input().split())))
dp = copy.deepcopy(graph)
for i in range(1, n):
for j in range(i):
dp[i+1][j] = max(dp[i+1][j], graph[i+1][j]+dp[i][j])
dp[i+1][j+1] = max(dp[i+1][j+1], graph[i+1][j+1]+dp[i][j])
print(max(dp[-1]))
2. 아래에서 올라가는 방법
n = int(input())
graph = []
for i in range(n):
graph.append(list(map(int, input().split())))
for i in range(n-1, 0, -1):
for j in range(i):
graph[i-1][j] += max(graph[i][j], graph[i][j+1])
print(graph[0][0])
🗝️keypoint
- 더할 수 있는 수 중, 가장 큰 수를 차례로 더해나가는 방법을 활용한다.
- 위에서 아래로 더해가는 방법을 택할 경우, 원본은 수의 비교를 위해 그대로 두어야 한다.
'코딩테스트 > Python' 카테고리의 다른 글
[Baekjoon] 18405. 경쟁적 전염 (0) | 2023.01.06 |
---|---|
[Programmers] Level 2. 문자열 압축 (0) | 2023.01.05 |
[Baekjoon] 18352. 특정 거리의 도시 찾기 (0) | 2022.12.29 |
[Programmers] Level 2. 두 큐 합 같게 만들기 (0) | 2022.12.26 |
[Leetcode] 77. Combinations (0) | 2022.12.02 |