백준 알고리즘 1932번: 정수 삼각형python

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

문제 접근

• 정수로 이루어진 삼각형이 주어짐.
• 위에서부터 아래로 내려오며, 인접한 수만 선택 가능.
• 최대 합을 구하라.

핵심 아이디어

• DP[i][j]: i행 j열까지 내려왔을 때의 최대 합
• 위에서 아래로 누적합을 계산하며 내려감.
• 각 위치에서 좌측 위 / 우측 위 중 큰 값을 선택해서 더함.

해답 및 풀이

import sys
input = sys.stdin.readline

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

for i in range(1, n):
    for j in range(i + 1):  # 각 행의 원소 개수는 i+1개
        if j == 0:
            triangle[i][j] += triangle[i - 1][j]  # 좌측 끝은 바로 위에서만 옴
        elif j == i:
            triangle[i][j] += triangle[i - 1][j - 1]  # 우측 끝은 대각선 왼쪽 위에서만 옴
        else:
            triangle[i][j] += max(triangle[i - 1][j - 1], triangle[i - 1][j])  # 중간은 두 곳에서 비교

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