프로그래머스 동적계획법(Dynamic Programming) 정수 삼각형 문제 풀이(Python, DP, Lv3)

정수 삼각형 문제 바로가기

문제 접근

그러하다
전형적인 dp문제이지 않나 싶다@!
그리디 문제라고 생각할 수 도 있는데 왼쪽에 큰 수를 넣어두고 맨 아래 오른쪽에 9999를 넣어두면 정답이 틀릴 수 있기에 모든 수를 확인해봐야 한다.
따라서 현재 값 + 위까지의 합 중 큰 값을 저장하여서 모든 수를 확인하면 정답이다.

문제 풀이

dp

dp[i][j] = triangle[i][j] + max(dp[i-1][j-1], dp[i-1][j])

위 식과 같이 현재까지의 합 중 큰 값 + 현재 삼각형의 수를 dp에 전부 저장하고 가장 dp의 마지막 배열 중 가장 큰 값이 최댓값이 된다.

제출 코드

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