패스트캠퍼스 6강 DP (1) 정수 삼각형

백준 1932번 정수 삼각형

문제링크 : https://www.acmicpc.net/problem/1932

tip

• DP 배열식엔 앞에 0을 추가하자
  + 아무것도 없다는 표시 가능
  + 인덱스 오류 방지

arr = [[0 for _ in range(N+1)] for _ in range(N+1)]

• DP를 풀 때는 DP식을 미리 정의하자

A[i][j] : (i, j)에 도착했을 때 최댓값

점화식 세우기

윗줄 (i-1)에서 바로 위(j)까지의 합 그리고 왼쪽(j-1)까지의 합 중 큰 것에 본인(arr[i][j] 더하기)

DP[i][j] = max(DP[i-1][j-1], DP[i-1][j]) + arr[i][j]

💡 풀이

import sys
input = sys.stdin.readline

N = int(input())
arr = [[0 for _ in range(N+1)] for _ in range(N+1)]
DP = [[0 for _ in range(N+1)] for _ in range(N+1)]

# 입력
for i in range(1, N+1):
    tmp = list(map(int, input().split()))
    for j in range(1, i+1):
        arr[i][j] = tmp[j-1]

# 반복문을 위에서부터 아래로 쭉 돌자
for i in range(1, N+1):
    for j in range(1, i+1):
        DP[i][j] = max(DP[i-1][j-1], DP[i-1][j]) + arr[i][j]

print(max(DP[-1]))