1932 - 정수 삼각형 / silver 1 / DP

"""
1932 - 정수 삼각형 / silver 1 / DP
"""
import sys

input = sys.stdin.readline

# 1. Input
n = int(input().rstrip())
arr = []
for _ in range(n):
    arr.append(list(map(int, input().split())))

# 2. DP
for i in range(1, n):
    for j in range(i + 1):
        # 맨 왼쪽
        if j == 0:
            arr[i][j] = arr[i][j] + arr[i - 1][0]
        # 맨 오른쪽
        elif j == i:
            arr[i][j] = arr[i][j] + arr[i - 1][i - 1]
        # 가운데
        else:
            arr[i][j] = arr[i][j] + max(arr[i - 1][j - 1], arr[i - 1][j])

# 3. Print
print(max(arr[n - 1]))

1. Input

n : 삼각형 크기

arr (list) : 삼각형 정보 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

[[7],

[3, 8],

[8, 1, 0],

[2, 7, 4, 4],

[4, 5, 2, 6, 5]]

 

2. DP (바텀 업 방식 / 0번 ~ 마지막 인덱스 까지)

2중 for문을 돌면서, 각 인덱스 위치의 값들을 순서대로 최대값으로 바꿔주려고 한다!

 

2차원 리스트를 표현 하기 위해서 2중 for문 사용하기 / i , j 

 

i = 1 일때,  [3,8] -> [10,15] 변환 / 이전 인덱스 값(7) + 현재 인덱스 값(3, 8)

[7],

[7+3, 7+8],

 

i = 2 일때, [8, 1, 0] -> [10+8, (10or15)+1, 15+0] 변환

즉, 가장 왼쪽 '8' 오른쪽 '0' 값들은 최대값이 되는 경우의 선택지가 하나이지만, 

가운데에 값인 '1' 은 선택지가 2개가 된다. 10 or 15 중 가장 큰 값 + 1

[7],

[10, 15],

[10+8, (10or15)+1, 15+0],

 

i = 3 일때, [2, 7, 4, 4] -> [18+2, (18or16)+7, (16or15)+4, 15+4] 변환

[7],

[10, 15],

[18, 16, 15],

[18+2, (18or16)+7, (16or15)+4, 15+4],

 

정리

- 각 인덱스 값들을 최대값으로 변경하고 나오기

- 가장 왼쪽에 있는 인덱스와 가장 오른쪽에 있는 인덱스는 선택지가 1개 이지만,

- 가운데 있는 인덱스들은 선택지가 2개이다.