[BOJ] 1932번 : 정수 삼각형 (Python)

🔒 문제

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

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

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

⌨ 입력

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

🖨 출력

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

📚 예제

Ex)

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

30

📌 풀이

dp[삼각형 높이][삼각형 가로] 로 행렬을 만들 것이다.

말로는 설명이 어려워서 그림으로 표현해봤다.

각 dp의 인덱스에는 각각의 위치까지의 최소값을 저장한다.

1. 삼각형의 높이가 1

dp[0][0]에는 정수 삼각형의 첫 값을 넣는다.
dp[0][0] = 정수 삼각형[0][0]

2. 삼각형의 높이가 2이상

dp의 n번째 행이라고 가정해보자. n번째 행에는 n개의 인수가 존재한다.
dp[n][m]이라고 표시하겠다.

1) m == 0 (인덱스 번호라 0부터 시작)

dp[n-1][m] = dp[n-2][m+1] + 정수 삼각형[n-1][m]

m==0 일때, 대각선을 타고 갈 수 있는 수는 오른쪽 위 대각선 밖에 없다.

2) m == 9

dp[n-1][m] = dp[n-2][m-1] + 정수 삼각형[n-1][m]

m == 9 일 때, 대각선을 타고 갈 수 있는 수는 왼쪽 위 대각선 밖에 없다.

3) 나머지

dp[n-1][m] = max(dp[n-2][m-1], dp[n-2][m+1]) + 정수 삼각형[n-1][m]

나머지들은 대각선 왼쪽 위와 오른쪽 위의 값들을 비교해서
그 중 더 큰 값을 dp[n-1][m]에 저장해야 한다.

🔑 python 코드

import sys
N = int(sys.stdin.readline())
tri = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]
dp = [[0 for _ in range(i)] for i in range(1,N+1)]
dp[0][0] = tri[0][0]

for i in range(1,N):
    for j in range(i+1):
        if(j==0):
            dp[i][j]=tri[i][j]+dp[i-1][j]
        elif(j == i):
            dp[i][j]=tri[i][j]+dp[i-1][j-1]
        else:
            dp[i][j]=tri[i][j]+max(dp[i-1][j-1],dp[i-1][j])

print(max(dp[N-1]))