백준 1932(정수 삼각형) - python

접근

최대값을 구하는 문제. 배열을 만들어서 dp[i][j]일때의 최대값을 dp[i][j]에 저장하자. dp[i-1][j-1], dp[i-1][j]가 각각 해당자리의 최대값이라면 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + cost[i][j] 가 된다. 해당 점화식을 보면 dp[i][j]를 구하기위해 dp[i-1] 만 필요하니 dp테이블을 모두 만드는것이아닌 1차원 2개만 만들면 메모리를 아낄 수 있다. 속도적인 측면에서는 그냥 배열을 쓰는게 좋겠지만 메모리를 절약하기 위해 1차원 배열 2개만을 이용해서 구현할 생각을 했다.

 

나의 코드

import sys
input = sys.stdin.readline


n = int(input())
dp = list(map(int,input().split()))
d = [-1 , 0]
for i in range(n-1):
    cost = list(map(int,input().split()))
    dp2 = []
    for j , c in enumerate(cost):
        maxv = 0
        for k in d:
            nextj = j + k
            if 0 <= nextj <= i:
                if maxv < dp[nextj]:
                    maxv = dp[nextj]
        dp2.append(maxv+c)
    dp = dp2

print(max(dp))