(파이썬) [알고리즘 문제 풀이] - 정수 삼각형 (프로그래머스)

설명

오늘은 프로그래머스에서 레벨3 문제 정수 삼각형을 풀어 보았습니다.

이렇게 삼각형이 주어집니다. 위에서부터 값을 더해가면서 내려오는데

아래로 내려갈때는 대각선 왼쪽과 오른쪽으로만 이동이 가능합니다.

이렇게 삼각형이 바닥까지 내려왔을때 가장 큰 값을 찾는 문제 입니다.

저는 이 문제를 다이나믹 프로그래밍을 써서 풀어보았습니다.

• 다이나믹 프로그래밍을 통해 찾은 값들을 저장할 테이블이 필요

• 꼭대기부터 차례 차례 값 더하기

• 내려갈수 있는 방향이 2개이기 때문에 겹치는 부분은 값을 비교해서 더 높은 값을 선택

위의 사진에 있는 삼각형을 예시로 들어보면,

첫번째 줄

2번째줄까지 계산

마지막줄까지 계산을 마친 상태

이 후에 마지막 줄에서 최대값을 찾아서 리턴해주면 알고리즘은 완성이 됩니다.

 

코드

 

def solution(triangle):
    dp = [[0 for i in range(row+1)] for row in range(len(triangle))]
    
    dp[0][0] = triangle[0][0]	#삼각형의 꼭대기 
    for i in range(len(triangle)-1):
        for j in range(i+1):
            dp[i+1][j] = max(dp[i][j]+triangle[i+1][j], dp[i+1][j])
            dp[i+1][j+1] = max(dp[i][j]+triangle[i+1][j+1], dp[i+1][j+1])

    return max(dp[-1])