백준 1932번 정수삼각형 (DP)

import sys
input = sys.stdin.readline
n = int(input())
tri = [list(map(int,input().rstrip().split())) for x in range(n)]
pf = [[0] * (i+1) for i in range(n-1)] + [tri[n-1]]
 
def per(i,z): # i번째 열의 z번째 수 중 더 큰 것을 골라주는 함수 
    temp = max(pf[i][z],pf[i][z+1])
    return temp

def que(i): #i번째 열에 대해 위에서 정의한 함수를 반복해서 적용
    lst = []
    for z in range(i):#map을 사용해도 된다.
        lst.append(per(i,z) + tri[i-1][z])
    return lst # 열을 다시 반환
i = n-1

while i !=0 : # que에서 반환해준 열을 i-1에 넣고, 반복 작업. 가능한 가장 높은 수가 제일 꼭대기로 올라온다.
    temp = que(i)
    pf[i-1] = temp
    i -= 1
print(pf[0][0])

힌트를 보지 않고 푼 첫번째 실버1 문제. 뿌듯하다.

그 동안 무작정 풀기만 했는데 이제 진짜 강의나 책을 읽어야겠다. 다이나믹 프로그래밍 넘어오면서 시간초과도 나고..

방학동안 목표는 골드 이상 다이나믹 프로그래밍, 그리디 알고리즘, 이분 탐색, 오프라인 쿼리를 푸는 것.

그 다음은 프로그래머스로 넘어가려한다.

 

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

1932번: 정수 삼각형