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

문제

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

풀이

dp 를 사용하여 푼 풀이
해당 칸에 생성될 수 있는 값들 중 가장 큰 수를 dp 배열 값에 할당한다.

col의 인덱스가 0 인 경우에는 생성될 수 있는 수가 dp 바로 윗칸과 해당 칸의 합 밖에 없다.
col의 인덱스가 -1 인 경우에는 생성될 수 있는 수가 dp 왼쪽 상단 칸과 해당 칸의 합 밖에 없다.

def solution(triangle):
    answer = 0
    dp = [[0] * len(row) for row in triangle]

    dp[0][0] = triangle[0][0]

    for row in range(1, len(triangle)):
        for col in range(0, len(triangle[row])):
            if col == 0:
                dp[row][col] = triangle[row][col] + dp[row - 1][col]
            elif col == len(triangle[row]) - 1:
                dp[row][col] = triangle[row][col] + dp[row - 1][col - 1]
            else:
                dp[row][col] = triangle[row][col] + max(dp[row - 1][col], dp[row - 1][col - 1])

    answer = max(dp[-1])

    return answer

다른 사람의 풀이

Bottom-Up 을 사용하면 col의 인덱스 조건문을 사용하지 않고 답을 구할 수 있다.

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