[DP] 프로그래머스 Lv3. 정수 삼각형 - Python

🗂️ 문제

링크: https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

 

💡 접근법

triangle[i][j]에 도달하는 방법은 두 가지 방법이 있다.

1. 대각선 왼쪽에서 내려오는 경우에는 dp[i][j] = dp[i-1][j-1] + t 이다.
2. 대각선 오른쪽에서 내려오는 경우에는 dp[i][j] = dp[i-1][j] + t 이다.

또한 인덱스가 0일 때(맨 왼쪽)는 오른쪽에서 내려오는 경우밖에 없고, -1일 때(맨 오른쪽)는 왼쪽에서 내려오는 경우밖에 없다.

 

😎 내 코드

def solution(triangle):
    answer = 0
    
    dp = []
    dp.append(triangle[0])
    
    for i in range(1, len(triangle)):
        temp = []
        for j, t in enumerate(triangle[i]):
            if j == 0:
                temp.append(dp[i-1][j] + t)
            elif j == len(triangle[i])-1:
                temp.append(dp[i-1][-1] + t)
            else:
                temp.append(max(dp[i-1][j-1] + t, dp[i-1][j] + t))
        dp.append(temp)
                
    return max(dp[-1])