[Algorithm] 1932. 정수 삼각형

1932: 정수 삼각형(DP)

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

• 문제 티어 : S1
• 풀이 여부 : Solved
• 소요 시간 : 43:57

정답 코드

# O(N^2)
import sys
input = sys.stdin.readline

N = int(input())
arr = [list(map(int, input().rstrip().split())) for _ in range(N)]

dp = [[0]*N for _ in range(N)] # 층 별 최대 값
dp[0][0] = arr[0][0]

for i in range(1, N):
  for j in range(i+1):
    # 대각선 왼쪽에서 내려온 경우
    if j > 0:
      left = dp[i-1][j-1] + arr[i][j]
    else:
      left = 0
    # 대각선 오른쪽에서 내려온 경우
    if j < i:
      right = dp[i-1][j] + arr[i][j]
    else:
      right = 0
    dp[i][j] = max(left, right)

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

접근 방식

처음엔 그리디라고 생각했지만, 이전 단계까지의 합을 구하는 문제이기에 DP로 풀이방법을 돌렸다.

대각선 왼쪽과 오른쪽에서 내려오는 값중 더 큰 값을 골라 누적합을 구하면 되는 문제!

배운점 또는 느낀점

DP는 코드 구현보다 점화식을 찾는 데에 정말 압도적으로 시간이 많이 든다.

관계 잘 파악하기!