BOJ-1932 정수 삼각형

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

문제 소개

크기가 n인 정수 삼각형의 맨 위층에서 맨 아래층까지 각 층에서 수를 하나씩 선택하여 누적된 수의 합의 최대값을 구한다.

문제 풀이

DP로 간단하게 풀이하였다. 리스트 arr에 삼각형 정보를 입력받은 후 반복문으로 위층에서부터 각 층의 값을 업데이트한다.

arr을 초기화 한 시점에 arr[i][j]는 i번째 층의 j번째 수를 의미하며, 각 층을 내려갈 때마다 대각선 왼쪽 위의 값과 대각선 오른쪽 위의 값 중 큰 값과 현재 위치 값을 더하여 업데이트한다.

이는 코드에서 arr[i][j] += max(arr[i - 1][j - 1], arr[i - 1][j])로 표현할 수 있다.

각 층에서 맨 좌/우측의 값은 한쪽 대각선으로만 내려올 수 있으므로 이는 이전 층의 맨 좌/우측의 값에 현재 위치 값을 더하도록 한다.

결과는 max(arr[-1])로 얻을 수 있다.

코드

import sys
input = lambda: sys.stdin.readline().rstrip()

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

for i in range(1, n):
    for j in range(i + 1):
        if j == 0:
            arr[i][j] += arr[i - 1][j]
        elif j == i:
            arr[i][j] += arr[i - 1][i - 1]
        else:
            arr[i][j] += max(arr[i - 1][j - 1], arr[i - 1][j])
print(max(arr[-1]))