[ Lv 3 ] 정수 삼각형

문제 설명

---

풀이 과정

---

1. dp를 활용하여야 효율성에서 통과 가능(탐색 X)

 

2. 현재 시점에서 이동 가능한 케이스가 두가지 있음. [i][j] -> [i+1][j], [i][j+1]

 

3. 따라서 맨 위에서 아래로 이동하면서 열 별로 현재 시점에서 이동 가능한 케이스 두가지를 이동하면서 누적합을 최댓값으로 계속 갱신해주는 방식으로 구현

 

---

import copy

def solution(triangle):
    answer = 0
    dp = copy.deepcopy(triangle)
    for i in range(len(triangle)-1):
        for j in range(len(triangle[i])):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + triangle[i+1][j])
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + triangle[i+1][j+1])
    
    answer = max(dp[len(triangle)-1])
    
    return answer