[Algorithm] 백준 1932 - 정수 삼각형 in Python(파이썬)

💡 백준 2193:

삼각형 규칙을 따라 자신까지의 합을 저장하며 DP 탐색

🌱 코드 in Python

알고리즘: Dynamic Programing

import sys

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

for i in range(1, n):
	g[i][0] += g[i - 1][0] # 해당 행의 첫번째 요소는 전 행의 첫번째 요소만 더할 수 있음
	g[i][i] += g[i - 1][i - 1] # 해당 행의 마지막 요소는 전 행의 마지막 요소만 더할 수 있음
	for j in range(1, i): # 그 외는 전 행의 j or j - 1 인덱스 중 큰 값을 합산
		g[i][j] += max(g[i - 1][j], g[i - 1][j - 1])
print(max(g[-1])) # 최종 행에서 더해진 가장 큰 값 출력

이번 문제는 삼각형의 왼쪽 대각선과 아래쪽 대각선으로만 내려올 수 있다는 조건을 통해 합을 더해 나가면 되는 문제였다

첫번째 요소와 마지막 요소는 각각 전행의 왼쪽 대각선, 오른쪽 대각선 밖에 받지 못하므로 그 값을 그대로 더하면 되지만,
가운데 있는 요소들은 양쪽에서 내려올 수 있기 때문에 값을 비교하여 메모이제이션 해야 한다

🧠 기억하자

1. 아직 코드를 깔끔하게 만드는 문제는 남아있지만,
   나 이정도 문제는 이제 조금 풀 수 있네..? 골드 가보자고..!

백준 1932 바로가기