[백준] 1932: 정수 삼각형

1932: 정수 삼각형

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

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번째 줄까지 정수 삼각형이 주어진다.

출력

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

풀이

 i번째 줄에 있는 한 수를 선택했을 때 그 수를 선택한 경로의 최댓값을 알기 위해서는 직전 줄에 선택한 원소의 대각선에 있는 원소까지의 경로 최댓값을 고려하면 된다. 따라서 dp를 (n+1)*(n+1) 이차원 리스트로 생성하였다. 이때 dp[i][j]는 i번째 줄의 j번째 원소를 선택한 경로의 최댓값을 말한다. 

 

 삼각형 형태이므로 양쪽 끝의 원소를 선택한 경우와 중간의 원소를 선택한 경우의 점화식을 따로 고려해야 한다.

1) 가운데 원소를 선택한 경우: dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j-1]

2) 양쪽 끝의 원소를 선택한 경우: dp[i][1] = dp[i-1][1] + arr[i][0], dp[i][i] = dp[i-1][i-1] + arr[i][i-1]

 참고로 이 문제에서도 arr의 인덱스를 보기 편하도록 1부터 시작하게 하기 위해 arr = [0]으로 선언하고 입력된 리스트를 append하는 식으로 저장했다.

# 1932: 401 - 다이나믹 프로그래밍 1 연습 - 정수 삼각형
n = int(input())
arr = [0]
for i in range(n):
    arr.append(list(map(int, input().split())))
dp = [[0] * (n+1) for i in range(n+1)]
dp[1][1] = arr[1][0]
for i in range(2, n+1):
    dp[i][1] = dp[i-1][1] + arr[i][0]
    dp[i][i] = dp[i-1][i-1] + arr[i][i-1]
    for j in range(2, i):
        dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j-1]
print(max(dp[n]))