[백준 c++] 1932번 정수 삼각형

문제

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

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
https://www.acmicpc.net/problem/1932

입력

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

출력

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

풀이

간단한 다이나믹 프로그램 문제였다. 각 층의 맨 왼쪽과 오른쪽은 하나의 케이스만 나오기에 별도로 처리하고, 나머지 중간에 끼어있는 부분들에 대해서 처리해주면 된다.
간단하게 7 / 3,8 / 8,1,0 이라 가정해본다면

• dp[0][0] = 7
• dp[1][0] = 7+3 = dp[0][0] + triangle[1][0]
• dp[1][1] = 7+8 = dp[0][0] + triangle[1][1]
• dp[2][0] = 10+8 = dp[1][0] + triangle[2][0]
• dp[2][1] = max(10+1,15+1) = max(dp[1][0], dp[1][1]) + triangle[2][1]
• dp[2][2] = 15+0 = dp[1][1] + triangle[2][2]

위 식에서 보이는 규칙을 정리해보자면
맨 왼쪽일 경우, 다시말해 각 층의 0번째 인덱스인 경우에는

• dp[i][0] = dp[i-1][0] + triangle[i][0]

맨 오른쪽일 경우, 다시말해 i번째 층의 i번째 인덱스인 경우에는

• dp[i][i] = dp[i-1][j-1] + triangle[i][i]

마지막으로 그 사이의 경우에는

• dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]

가 성립한다!

위 점화식을 토대로 구현하면 된다

#include <algorithm>
#include <iostream>
using namespace std;

int main()
{
    int n;
    int arr[501][501];
    int dp[501][501];
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            cin >> arr[i][j];
        }
    }

    int ans = arr[0][0];
    dp[0][0] = arr[0][0];
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (j == 0)
                dp[i][j] = dp[i - 1][0] + arr[i][0];
            else if (j == i)
                dp[i][j] = dp[i - 1][j - 1] + arr[i][j];
            else
                dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];

            ans = max(ans, dp[i][j]);
        }
    }

    cout << ans << '\n';

    return 0;
}