[BOJ] 정수 삼각형

---

코드

import sys
input = sys.stdin.readline

tri = []

# 입력
row = int(input())
for _ in range(row):
    tri.append(list(map(int, input().split())))

# 각 숫자에 대해 위쪽 줄 왼쪽, 오른쪽까지의 max값 중 큰 값을 더한다
for i in range(1, row):
    for j in range(len(tri[i])):
        if j == 0:    # r행의 첫번째수
            tri[i][j] += tri[i-1][j]
        elif j == len(tri[i])-1:    # r행의 마지막수
            tri[i][j] += tri[i-1][j-1]
        else:
            tri[i][j] += max(tri[i-1][j-1], tri[i-1][j])

# 정답 출력: 마지막 행의 가장 큰 값
print(max(tri[row-1]))

결과

풀이 방법

• 다이나믹 프로그래밍을 활용하여 해결하였다.
• 삼각형의 각 수에 대해, 자신의 윗줄 왼쪽과 오른쪽 수들 중 큰 수를 자신과 더하면, 각 수에 도달할때까지의 최대값만을 저장할 수 있게 된다.
• 마지막 행까지 위 계산을 수행한 다음, 마지막 행의 최대값을 출력하면 정답이다.
• 이차원 배열을 사용하여 삼각형의 각 행의 수들을 입력받았다.

---