[Python] 백준 1932번. 정수 삼각형

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

1932번: 정수 삼각형

문제 설명:

삼각형에서 아래에 있는 수를 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램

 

• 전에 저장된 값을 활용하고 있다.
  • 7일때 3과 8은 7을 활용하여 최댓값을 구해야한다.
• 반복적이다.
  • 3은 8을 더하고/ 1을 더해 다음값을 저장한다.
  • 8은 1을 더하고/ 0을 더해 다음값에 저장한다.

=> 다이나믹 프로그래밍이다.

 

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

 

풀이해설:

• i는 2차원 배열의 길이의 인덱스이다. 즉 0~n까지 
• j = 0 일때 다음값은 이전에 저장된 dp[i-1][0]의 값에 현재 자기자신 dp[i][0]을 더한값이다.
• j = 0 이상일때 다음값은 이전의 j-1의 값(dp[i-1][j-1))과 이전의 j의 값(dp[i-1][j])의 값의 최댓값을 저장한다.
• j = i 와 같아지면 dp[i-1][j-1]의 값에 자기자신을 더한값이다. 

import sys

input = sys.stdin.readline
n = int(input())
dp = []
for i in range(n):
    dp.append(list(map(int, input().split())))

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

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