[백준 1932] 정수 삼각형

문제

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

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

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

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

입력

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

출력

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

---

풀이

먼저 문제를 보고 바로 떠오른 방식은 피라미드 형태의 리스트를 선언하고

dp[n][x] = max(dp[n-1][x-1], dp[n-1][x])+score[n] 와 같은 점화식으로 각 층의 해당 위치까지의 최대값을 저장

 

코드를 작성하기 전 시간복잡도를 체크해보았다

삼각형의 높이는 최대 500이고 삼각형의 크기가 가장 큰 경우 n(n+1)/2 에 500을 대입할 경우 나오는 값이 충분히 감당 가능해 보여 코드를 작성하였다

 

# 정수 삼각형
import sys

n = int(sys.stdin.readline())
dp = [] # 각 층까지의 최대값 담을 공간
dp.append([int(sys.stdin.readline())])  # 첫번째 층 사전처리

for i in range(1,n):
    scores = list(map(int,sys.stdin.readline().split()))
    dp.append([])
    for j in range(len(scores)):
        if j==0:
            dp[i].append(dp[i-1][j]+scores[j])  # n번째 줄 첫번째 원소 처리
        elif j==i:
            dp[i].append(dp[i-1][j-1]+scores[j])    # n번째 줄 마지막 원소 처리
        else:
            dp[i].append(max(dp[i-1][j-1],dp[i-1][j])+scores[j])    # 중간 원소들 처리

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

첫번째 층을 미리 초기화하고 이후의 층들은 첫 원소와 마지막 원소를 분리하여 점화식을 적용시켰다