이해

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

• 위 모습은 크기가 5인 정수 삼각형이다.
• 삼각형의 크기 n과 정수 삼각형이 주어질 때, 맨 위층부터 시작해서 아래에 있는 수 중 하나를 선택하면서 맨 아래로 내려올 때 선택된 수의 합의 최댓값을 출력하라.

계획

• dynamic programming 유형으로 접근, 점화식은 다음 아래와 같다.

  dp[i][j]: (i, j)까지 내려왔을 때, 선택된 수의 합의 최댓값
  arr[i][j]: 정수 삼각형의 (i, j) 위치에 있는 수
  
  dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + arr[i][j]
  

실행

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * (i + 1) for i in range(n)]

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

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

개선

• Top-Down 방식으로 dp테이블 업데이트를 진행하면 훨씬 간단하게 구현할 수 있다.
• 따로 dp테이블을 선언하지 않고 삼각형 배열만 가지고 업데이트를 할 수 있다.

n = int(input())

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

for i in range(n - 2, -1, -1):
    for j in range(i + 1):
        data[i][j] = max(data[i][j] + data[i + 1][j], data[i][j] + data[i + 1][j + 1])

print(data[0][0])

회고

• 예전에 푼 문제였어서 쉽게 풀었다.