1932번. 정수 삼각형

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

 

 

선행 문제인 RGB거리 문제를 풀었다면 쉽게 해결할 수 있는 문제였다.

추상화가 필요없다는 점에서 이게 더 쉬운 것 같기도...

마찬가지로 이전 행까지의 값을 저장해놓고 있어야 하기 때문에 동적 프로그래밍에 해당하는 문제이다.

bottom-up으로 찾고 싶은 높이까지 최댓값을 각각 열마다 저장해나가는 것이 포인트다.

파이썬이기 때문에 삼각형 모양의 배열 선언이 비교적 쉬웠던 것 같다.

import sys
n = int(sys.stdin.readline())
tri = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
val = [[0]*i for i in range(1, n+1)]

val[0][0] = tri[0][0]

for row in range(1, n):
    if row == 1:
        val[1][0] = tri[1][0] + val[0][0]
        val[1][1] = tri[1][1] + val[0][0]
    for col in range(row+1):
        if col == 0:  # 제일 첫 번째
            val[row][0] = tri[row][0] + val[row-1][0]
        elif col == row:  # 제일 마지막번째
            val[row][-1] = tri[row][-1] + val[row-1][-1]
        else:  # 그게 아닌, 대각선 방향 두 개 중에 선택해야 하는 것들
            val[row][col] = tri[row][col] + max(val[row-1][col-1], val[row-1][col])

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