백준 22.02.09. 1932번 - 정수 삼각형

n = int(input())

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

idx = tri[1].index(max(tri[1]))
for i in range(1, n):
    tri[i][idx] += max(tri[i-1][idx-1:idx+1])
    idx = tri[i].index(max(tri[i]))


print(max(tri[-1]))

경로에 있는 최댓값만 골라서 더하는 방식으로 작성했습니다.

하지만 지나치는 경로의 합이 최대인 것을 구하는 것이 문제이므로 각 줄마다의 경로에서 최댓값을 고르는 것이 정답은 아닙니다.

n = int(input())

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

for i in range(1, n):
    for j in range(len(tri[i])):
        if j + 1 > len(tri[i-1]):
            tri[i][j] += tri[i-1][j-1]
        elif j-1 < 0:
            tri[i][j] += tri[i-1][0]
        else:
            tri[i][j] += max(list(tri[i-1][j-1:j+1]))

print(max(tri[-1]))

• 주어진 수들을 경로대로 따라가며 최댓값을 저장하여 마지막에 출력하도록 했습니다.
• 정수삼각형에서의 경로는 왼쪽아래 또는 오른쪽 아래로 갈 수 있는데, 이는 [인덱스] 또는 [인덱스 + 1]의 인덱스를 가진다고 볼 수 있기 때문에 위와 같이 식을 짰습니다.
• 2번째 줄 부터 합계를 시작했으며 각 요소마다 전 줄의 [인덱스-1] 또는 [인덱스]에 해당하는 요소 중에서 최댓값을 더해주었습니다.
• 하지만 인덱스가 0 또는 최댓값일 때는 범위때문에 오류가 날 수 있으므로 분기를 3갈래로 나누어주었습니다.