[DP] 프로그래머스 Lv3. 정수 삼각형 - Python

🗂️ 문제

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

프로그래머스

 

💡 접근법

DP의 top-down 방식으로 풀었다.

triangle을 모두 탐색하면서 값을 업데이트 해나갔다.

 

현재 위치까지 도달하는 모든 경로 중 최댓값을 저장해야 한다. 따라서 위의 칸의 대각선 두 값 중 더 큰 값을 선택하여 더한다. 만약 대각선에 값이 존재하지 않는다면, 이는 삼각형의 범위를 벗어난 것이므로 이를 따로 처리해야 한다.

 

점화식은 dp[i][j] = dp[i-1][j-1] + dp[i-1][j] (i>=1, j>=0)이다.

 

😎 내 코드

def solution(triangle):
    for i in range (1, len(triangle)):
        for j in range (len(triangle[i])):
            if i-1 >= 0 and j != 0 and j != len(triangle[i-1]):
                triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
            elif j == 0:
                triangle[i][j] += triangle[i-1][j]
            elif j == len(triangle[i-1]):
                triangle[i][j] += triangle[i-1][j-1]
    
    return max(triangle[-1])

 

👀 배운 코드

def solution(triangle):

    height = len(triangle)

    while height > 1:
        for i in range(height - 1):
            triangle[height-2][i] += max([triangle[height-1][i], triangle[height-1][i+1]])
        height -= 1

    answer = triangle[0][0]
    return answer

bottom-up 방식의 풀이이다.

top-down 방식과 반대로, 업데이트 할 위치에 대각선 아래 두 삼각형 중 더 큰 값을 더해가면 된다.