프로그래머스 정수 삼각형 파이썬

프로그래머스 파이썬 정수 삼각형 프로그래머스 정수 삼각형 파이썬 파이썬 프로그래머스 정수 삼각형 파이썬 정수 삼각형 프로그래머스 정수 삼각형 프로그래머스 파이썬 정수 삼각형 파이썬 프로그래머스

정수 삼각형

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

문제 단순화

• 삼각형의 정보가 들어 있는 trianlge 배열이 있다.
• 맨 위쪽 요소부터 대각선으로 이어진 요소로 내려오면서 값을 합칠 때, 맨 밑에 도착했을 때의 최댓값을 리턴한다.

문제풀이

• 1차원 dp를 만들어 맨 위쪽 요소부터 탐색을 시작한다.
• triangle[n]에서 더할 수 있는 dp[n-1]의 요소들을 비교하여, 최대값을 dp[n]에 추가한다.
• dp의 마지막 요소 중에 최대값을 리턴한다.

코드

def solution(triangle):
    n = len(triangle)
    dp = [[] for _ in range(n)]
    dp[0] = triangle[0]
    for i in range(1,n):
        for j in range(i+1):
            if j == i:
                dp[i].append(triangle[i][j] + dp[i-1][j-1])
            elif j == 0:
                dp[i].append(triangle[i][j] + dp[i-1][j])
            else:
                dp[i].append(max(triangle[i][j] + dp[i-1][j], triangle[i][j] + dp[i-1][j-1]))
    return max(dp[n-1])