백준 1932 정수 삼각형 (Python)

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

1932번: 정수 삼각형

일단 문제가 DP이기 때문에 보자마자 단계가 있는지 확인한다.

 

일단 바로 각 층으로 단계를 구별할 수 있을 것 같다.

그렇게 단계를 나누면, 각 단계별로 영향을 받는 것은 해당 단계의 전 단계이다.

전 단계를 보고 해당 단계의 최대값을 구하며 내려가면 될 것 같다.

 

import sys

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

max_list = [0 for i in range(n)]

for i in range(n):
    level = list(map(int, sys.stdin.readline().split()))
    cur_max_list = list()

    for t in range(i+1):
        if t == 0:
            cur_max_list.append(max_list[0] + level[0])
        elif t == i:
            cur_max_list.append(max_list[-1] + level[i])
        else:
            cur_max_list.append(max(max_list[t-1], max_list[t]) + level[t])
    max_list = cur_max_list

print(max(max_list))

 

각 층의 첫 번째 칸과 마지막 칸은 경우가 그냥 하나 밖에 존재하지 않는다.

그냥 위의 칸 + 현재 칸이다.

해당 값은 그냥 바로 구해서 넣어줄 수 있도록 하고, 그 사이의 칸들은 윗 단계에서 내려올 수 있는 2가지 수 중에서 큰 값을 가져와 본인의 수와 더해 최대값을 구할 수 있도록 하였다.