[Baekjoon] 1932. 정수 삼각형

🔗 Problem Link

1932번: 정수 삼각형

---

❔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

1. 더할 수 있는 수 중, 가장 큰 수를 차례로 더해나가는 방법을 활용한다.
2. 위에서 아래로 더해가는 방법을 택할 경우, 원본은 수의 비교를 위해 그대로 두어야 한다.