백준 1932 파이썬(DP)

 

역시나 DP문제이므로 처음엔 점화식을 구해보려고 생각해보았다.

 

그러나 이전처럼 뭔가 깔끔하고 정리가 딱 되는 점화식이 생각나지 않아서

각 층마다의 최대값을 모두 구하는 방식으로 문제를 풀었다.

각 층의 첫번째 값과 마지막 값은 바로 직전 층의 값을 그대로 더해주면 되었고

그 이외의 값들은 위에 층의 더해질 수 있는 두가지 값 중 큰 값을 더해주는 방식으로 풀었다.

 

• 코드

# 1932 - 정수삼각형
# 아이디어는 각 층마다 최대값을 다 구한뒤 최대값을 찾아서 출력한다

import sys
input = sys.stdin.readline

n = int(input())
triangle = []
for _ in range(n):
    triangle.append(list(map(int,input().split())))

for i in range(1,n):
    for j in range(len(triangle[i])):
        if j == 0:
            triangle[i][j] += triangle[i-1][j]
        elif j == len(triangle[i])-1:
            triangle[i][j] += triangle[i-1][j-1]
        else:
            triangle[i][j] += max(triangle[i-1][j-1],triangle[i-1][j])

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

 

예전에 DP를 공부하려고 동영상들을 찾아보다가 이 예제로 설명한 동영상이 기억이나서 링크를 걸어놓았다.

이 문제를 그리디로 푼다면 잘못된 결과를 낸다는 것을 보여주었고

DP로는 어떻게 접근해서 풀어야하는지 잘 설명해주셨다.

 

youtu.be/2RwlzBDhGh4?t=469