(Python/🥈1)백준 알고리즘 1932번: 정수 삼각형

문제 출처;https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

풀이:

 

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

def solution(triangle):

    dp = [[0]*len(triangle) for i in range(len(triangle))]
    dp[0][0] = triangle[0][0]
    for i in range(0, len(triangle)-1):
        for j in range(len(triangle[i])):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + triangle[i+1][j]) 
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+triangle[i+1][j+1]) 
    return max(dp[-1])

N = int(input())
triangle = []
for i in range(N):
    triangle.append(list(map(int,input().split(' '))))
print(solution(triangle))

 

dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + triangle[i + 1][j]) 

# 각줄 첫번째 자리와 중간 최댓값
# dp[i+1][j] 로 이전에 위에 두개 더한게 저장되어있음

dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + triangle[i + 1][j + 1])

# 각 줄 마지막 자리와 중간값 최댓값비교
# dp[i + 1][j + 1] 로 이전에 위에 두개 더한게 저장되어있음

 

 

며칠전 dp를 공부하면서 프로그래머스에서 푼 문제랑 동일하다.

https://windy7271.tistory.com/entry/PythonLV3-%EC%A0%95%EC%88%98-%EC%82%BC%EA%B0%81%ED%98%95

(Python/LV3) 정수 삼각형