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

💻 문제 - Lv.3

👉 제출 코드

def solution(triangle):
    depth = len(triangle)
    for row in range(1, depth):
        for col in range(row+1):
            if col == 0:
                max_value = triangle[row-1][col]
            elif col == row:
                max_value = triangle[row-1][col-1]
            else: # 안쪽에 있는 수일 때
                max_value = max(triangle[row-1][col-1], triangle[row-1][col])
            triangle[row][col] = triangle[row][col] + max_value
    return max(triangle[depth-1])

새로운 배열을 생성하지 않고 triangle 배열에 최댓값을 갱신하는 동적계획법을 사용하였다. 아래 칸으로 이동할 때 대각선 방향으로 오른쪽 또는 왼쪽으로 이동 가능하므로 크게 두가지 케이스로 나뉜다.

1. 안쪽에 있는 수일 때
   오른쪽과 왼쪽에서 오는 수 중에 최댓값을 구해야한다.
2. 양쪽 끝에 있는 수일 때
   한 방향으로만 오기 때문에 최댓값을 구하지 않아도 된다.

🙏 다른 사람의 풀이 보기

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

위에서부터 아래로가 아닌 아래서 위로 올라가는 풀이이다.