[프로그래머스][python] 정수삼각형 - DP

문제

• 프로그래머스 정수삼각형
• Level 3
• Link

코딩테스트 연습 - 정수 삼각형

 

나의 풀이

동적계획법으로 풀면 되는 문제다. 주어진 2차원 배열의 첫 번째 배열부터 그 다음 배열에 값을 더해나가면서 저장해준다. 가장 마지막의 배열의 최대 값을 리턴해준다. 

# https://programmers.co.kr/learn/courses/30/lessons/43105


"""
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
"""

def solution(triangle):
    
    for j in range(1, len(triangle)):
        for i in range(len(triangle[j])):
            prevlevel = triangle[j - 1]
            level = triangle[j]
            
            if i == 0:
                level[i] += prevlevel[i]
            elif i == len(level) - 1:
                level[i] += prevlevel[i - 1]
            else:
                if j == 1:
                    level[i] += prevlevel[i - 1]
                else:
                    bigger = max(prevlevel[i - 1], prevlevel[i])
                    level[i] += bigger
            
    return max(triangle[-1])