💡 동적 계획법

다이나믹 프로그래밍(dynamic programming)

동적 계획법(DP)는 큰 문제를 작은 문제로 나누어 푸는 알고리즘이다.
앞에서 구했던 답을 뒤에서도 답을 재활용하여 이용하는 방식이다.

📢 정수 삼각형 1932번 문제

백준 문제 링크

🔎 풀이

사용언어:PYTHON
대각선으로 더해주면서 내려오는데, 여러 대각선을 더할 수 있으면 큰 값을 더하면서 내려온다.

풀이 참고 링크
풀이 참고 링크2

🔎 코드

import sys
n = int(input())
num = [list(map(int, input().split())) for _ in range(n)]

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


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