title: "[프로그래머스] 정수 삼각형 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/43105"
description: "프로그래머스 Level 3 문제 [정수 삼각형]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

def solution(triangle):
    # 전형적인 DP 문제입니다.
    N = len(triangle)
    dp = [[-1 for _ in range(N)] for _ in range(N)]
    
    dp[0][0] = triangle[0][0]
    for r in range(1, N):
        for c in range(r + 1):
            
            candidates = []
            candidates.append(dp[r-1][c])
            if c != 0:
                candidates.append(dp[r-1][c-1])
            
            dp[r][c] = max(candidates) + triangle[r][c]
            
    return max(dp[N-1])

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges