프로그래머스 코딩테스트 - 정수 삼각형(Lv3)

문제 풀기

DP table을 만들어 쉽게 풀 수 있는 문제.

• 계산 방법의 경로를 역추적하면 바로 위에서 오거나, 그 옆에서 오거나 두가지 경우임.
• 양 끝에 있는 건 예외처리 고고.

def solution(triangle):

    n = len(triangle[-1])
    dp = [[-1]*j for j in range(1,n+1)] # 테이블 생성
    dp[0]=triangle[0]
    # print(dp)
    
    for i in range(n):
        if i==0:
            continue;
        for j in range(i+1):
            if j==0:
                
                dp[i][j] = dp[i-1][j] + triangle[i][j]
            elif j==i:
                dp[i][j] = dp[i-1][j-1] + triangle[i][j]
            else:
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) +  triangle[i][j]    
    return max(dp[-1])