[백준] 정수 삼각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

dp를 이용하는 문제입니다.

 

이전에는 아래에서 위로 올라가는 다른 방식으로 풀이를 하였는데 dp로도 한번 다시 풀어보았습니다. 

https://life318.tistory.com/26

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

 

DP를 이용한 풀이

<Solution>

다음과 같은 아이디어를 통해 중복된 계산 없이 코드를 진행할 수 있습니다. 

 

실제 구현은 아래와 같습니다.

import sys

n = int(sys.stdin.readline().rstrip())

triangle = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

array = [[0]*i for i in range(1,n+1)]
array[0][0] = triangle[0][0]

for i in range(1, n):
    # left
    array[i][0] = triangle[i][0] + array[i-1][0]
    # right
    array[i][i] = triangle[i][i] + array[i-1][i-1]
    # others
    for j in range(1, i):
        array[i][j] = triangle[i][j] + max(array[i-1][j-1], array[i-1][j])

print(max(array[n-1]))