[백준] 1932번 - 정수 삼각형 (python)

문제

위에서부터 시작해 아래로 내려오며 각 층의 수를 하나씩 선택해 더할 때, 총합이 최대가 되는 경로를 구하여라

 

문제 바로가기

1932번: 정수 삼각형

 

풀이

• 파란색 글씨가 입력으로 들어온 삼각형 모양의 숫자이고, 빨간색 글씨가 각 경우에서 누적합이 최댓값이 되는 경우이다. 코드에서 파란색이 num, 빨간색이 d에 해당한다.
• 맨 위 꼭짓점은 더할 수 있는 값이 없으므로 자기 자신이다.

• 왼쪽 변과 오른쪽에 있는 숫자의 경우, 자기 자신에 바로 위에 있는 숫자만 더할 수 있다.
• 중앙에 있는 숫자의 경우, 자기 자신에 윗줄의 양옆 숫자 중 최댓값을 더한다. → 그림에서 삼각형을 보면 양옆이라서 d[i, j] = max(d[i-1, j], d[i-1, j+1]) + num[i, j]인 줄 알았는데, 2차원 리스트의 인덱스를 생각해보면 각 행의 열 인덱스가 0부터 시작하기 때문에 윗줄의 양옆 숫자가 아닌, 윗줄의 왼쪽과 바로 윗줄 숫자를 봐야 한다.

 

코드

import sys
read = sys.stdin.readline

n = int(input())
num = []
for i in range(n):
    num.append(list(map(int, read().split())))
d = [[0] * i for i in range(1, n+1)]  # 누적 합

print('num:', num)
print('d:', d)


for i in range(n):
    for j in range(i+1):
        # 맨 위 꼭지점
        if i == 0 and j == 0:
            d[i][j] = num[i][j]
        # 왼쪽 변에 해당하는 경우
        elif j == 0:
            d[i][j] = d[i-1][0] + num[i][j]
        # 오른쪽 변에 해당하는 경우
        elif j == i:
            d[i][j] = d[i-1][-1] + num[i][j]
        # 가운데 숫자인 경우
        else:
            d[i][j] = max(d[i-1][j-1], d[i-1][j]) + num[i][j]

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