[프로그래머스 43105 파이썬] 정수 삼각형 (level 3, DP)

알고리즘 유형 : DP(Dynamic Programming)
풀이 참고 없이 스스로 풀었나요? : O

https://school.programmers.co.kr/learn/courses/30/lessons/43105?language=python3

소스 코드(파이썬)

import sys
input = sys.stdin.readline

def solution(triangle):
    DP = [[0]*len(triangle) for _ in range(len(triangle))]
    DP[0][0] = triangle[0][0]
    
    # 1행부터 마지막 행까지
    for width in range(1, len(triangle)):
        # 행의 열 채우기(이전 행의 두 DP 값 중 큰 값과
        # 자기 자신(triangle)을 더한 것으로 채움)
        for col in range(width+1):
            if col-1 >= 0:
                DP[width][col] = DP[width-1][col-1] + triangle[width][col]
            
            if DP[width-1][col]:
                DP[width][col] = max(DP[width][col], DP[width-1][col] + triangle[width][col])
    
    return max(DP[-1])

풀이 요약

1. 점화식은 다음과 같다.

   DP[row][col]
   = DP[row-1][col-1] + triangle[row][col] (if col != 0)
   = DP[row-1][col] + triangle[row][col] (if col != width)
   = max(DP[row-1][col-1] + triangle[row][col], DP[row-1][col] + triangle[row][col]) (else)

   이 걸 바텀업으로 삼각형의 두 번째 행부터 채워나가면 된다.

배운 점, 어려웠던 점

• 간단한 문제였다. 원본은 그대로 보존하는게 나을 것 같아 따로 DP 리스트를 할당해서 풀었다.