[프로그래머스 / Python] 정수 삼각형

문제 링크: programmers.co.kr/learn/courses/30/lessons/43105

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

 

문제 설명

거쳐온 숫자들의 합의 최댓값을 저장하는 dp 테이블을 생성합니다. 

 

triangle[i][j]에 도달하는 방법은 두 가지 방법이 있습니다. 

1. triangle[i - 1][j - 1]에서 triangle[i][j]로 가기
2. triangle[i - 1][j]에서 triangle[i][j]로 가기

dp[i][j]는 위 두 가지 값 중에서 최댓값을 저장합니다. 

 

 

예를 들어 triangle 배열이 다음과 같다면

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

dp 테이블은 다음과 같이 계산됩니다. 

7
10(7 + 3)	15(7 + 8)
18(10 + 8)	16(15 + 1)	15(15 + 0)
20(18 + 2)	25(18 + 7)	20(16 + 4)	19(15 + 4)
24(20 + 4)	30(25 + 5)	27(25 + 2)	26(20 + 6)	24(19 + 5)

dp 테이블 계산이 끝난 후에 마지막 줄의 원소 중에서 최댓값을 반환합니다. 

 

 

 

소스코드

def solution(triangle):
    # dp 테이블 초기화
    dp = [[0] * len(triangle) for _ in range(len(triangle))]
    dp[0][0] = triangle[0][0]
    # 거쳐간 숫자의 최댓값 구하기
    for i in range(0, len(triangle) - 1):
        for j in range(len(triangle[i])):
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + triangle[i + 1][j])
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + triangle[i + 1][j + 1])

    return max(dp[-1]) # dp 테이블의 마지막 원소들 중 최댓값 반환