from palette import colorful_colors

[백준] 1932 정수 삼각형 with 파이썬 본문

알고리즘/알고리즘 with 파이썬

[백준] 1932 정수 삼각형 with 파이썬

colorful-palette 2023. 11. 13. 21:03
import sys
input = sys.stdin.readline

# 입력받기
N = int(input())
for i in range(N):
    d.append(list(map(int, input().split())))

# 초기값
if N > 2:
    d[1][0] = d[0][0] + d[1][0]
    d[1][1] = d[0][0] + d[1][1]

# 메모이제이션 하면서 계산
for i in range(2, N):
    for j in range(0, i+1):
        if j == 0:
            d[i][j] = d[i - 1][0] + d[i][j]
        elif j == i:
            d[i][j] = d[i - 1][j - 1] + d[i][j]
        else:
            d[i][j] = max(d[i-1][j-1] , d[i-1][j]) + d[i][j]

# 결과 출력
print(max(d[N-1]))