[백준/1932/파이썬] 정수 삼각형

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

1932번: 정수 삼각형

Problem

• 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라.

조건

• 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
• 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
• 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

SOL

완전탐색으로 푼다면, 역시 ,2^N이 나오는 친구이다.

DP로 망설임 없이 접근했고, DP table을 다음과 같이 정의했다. 

• DP[n][k] = max(DP[n-1][k-1], DP[n-1][k]) + board[n][k]
• DP[n][0] = DP[n-1][0] + board[n][0]

항상, bottom up을 쓰는 건, 반복문을 쓴다는 거니까, 반복을 어떻게 돌아줄지 고민을 해야한다.

board 입력을 한줄한줄 받았기 때문에, k의 범위가 n까지가 아님.

즉, n+1까지여서, Out of index를 방지해주기 위해서, 반복횟수도 조절해주었다.

#bottom up
N= int(input())
board=[list(map(int,input().split())) for _ in range(N)]

DP = [[0]*N for _ in range(N)]
DP[0][0] = board[0][0]

for i in range(1,N):
    DP[i][0] = DP[i-1][0]+board[i][0]

for i in range(N):
    for j in range(1,i+1):
        DP[i][j] = max(DP[i-1][j-1],DP[i-1][j])+board[i][j]

print(max(DP[N-1]))
#print(board)