📕문제

[Baekjoon] 1932. 정수 삼각형

문제 설명

정수 삼각형에서 맨 위부터 시작해 아래에 있는 수 중 하나를 선택해서 내려오면서 더할 때 최댓값을 구하는 문제다.

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

위 그림에선 최댓값이 $7+3+8+7+5 = 30$ 이 된다.

---

📝풀이

import sys
read = sys.stdin.readline

n = int(read())
memo = []
for _ in range(n):
    memo.append(list(map(int, read().split())))

for i in range(1, n):
    for j in range(i + 1):
        if j == 0:
            memo[i][j] += memo[i-1][j]
        elif j == i:
            memo[i][j] += memo[i-1][j-1]
        else:
            memo[i][j] += max(memo[i-1][j-1], memo[i-1][j])

print(max(memo[n-1]))

• 아래로 내려가면서 숫자가 더해지는 경우는 세가지가 있다.
  • 가장 왼쪽에 있는 숫자: 해당 숫자를 더한다.
  • 가장 오른쪽에 있는 숫자: 해당 숫자를 더한다.
  • 그 외: 왼쪽 가지와 오른쪽 가지에서 내려온 합계 중 더 큰 수에 해당 숫자를 더한다.
• 마지막 행의 최댓값이 정답이 된다.