[백준] 1932 : 정수 삼각형 - Python

정수 삼각형

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

import sys
sys.stdin = open("input.text", "rt")
input = sys.stdin.readline

#내려갈때마다 대각선 왼쪽 or 대각선 오른쪽만 선택
#현재층의 i번째 인덱스면 다음층의 i, i+1 둘중하나 선택가능
#현재의 선택이 미래에 영향. 그리디 x dp로 풀어야함

n = int(input())
dp = [[0] * 501 for _ in range(n+1)]
data = [[0]]
for _ in range(n):
    temp = list(map(int, input().split()))
    temp.insert(0,0)
    data.append(temp)

dp[1][1] = data[1][1] #1층 1번 인덱스 자명한건 미리 초기화
res = 0
for i in range(2,n+1): #2번째 층부터 탐색.
    for j in range(1,i+1):
        if j == 1:
            dp[i][j] = dp[i-1][1] + data[i][1]
        elif j == i:
            dp[i][j] = dp[i-1][j-1] + data[i][j]
        else:
            caseA = dp[i-1][j-1] + data[i][j]
            caseB = dp[i-1][j] + data[i][j]
            dp[i][j] = max(caseA, caseB)

for i in range(1,n+1):
    res = max(dp[n][i], res)
    
print(res)

👻 코멘트

아래에서 더해가면서 내려올 때 현재 결정이 다음번 결정에 영향을 끼친다. dp로 풀어야함

• 조건이 붙는데, 맨 왼쪽 맨 오른쪽은 따로 해주면 된다 !

이제 조금씩 기존값들은 저장해놓는 구조가 이해가 가는데... 이전까지의 최댓값 + 현재값 이런 식으로 엮는 방식 기억 !

• 나는 0번 인덱스를 사용하기 싫어서 dp도 i는 1번부터 그리고 호실도 1번부터 사용하기 위해 위와같이 짰다.