Python - [백준]1932-정수삼각형

출처

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

문제

삼각형을 내려올때 선택한 값의 최대값을 찾는 문제이다.

접근방법

층별로 내려올때의 최대값을 기록해주는 DP를 사용하여 해결하였다.
3가지의 경우로 나누어 생각 할 수 있다.

1. 맨 왼쪽의 경우, 바로 위에것을 선택하는 경우 밖에 없다.
2. 가운데 원소들의 경우, j-1과 j중 최대값을 선택 할 수 있다.
3. 맨 오른쪽의 경우, j-1을 선택하는 경우 밖에 없다.

이렇게 구성된 점화식을 구현하면 된다.

풀이

주어진 배열과 크기와 모양이 같은 DP배열을 하나 더 선언하고, 2번째 층 부터 아까 구한 점화식을 사용하여 코드를 짜면 된다.

import sys
input = sys.stdin.readline

n = int(input())
arr = [list(map(int,input().split())) for i in range(n)]
dp = []
for i in range(n):
    dp.append([0]*(i+1))

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