문제

백준 1932번 문제

코드

#include <bits/stdc++.h>

using namespace std;

int N;
int arr[504][504];
long long dp[504][504];

int main()
{
    cin >> N;

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

    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][j] + arr[i][j];
            }
            else if (j == i)
            {
                dp[i][j] = dp[i - 1][j - 1] + arr[i][j];
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + arr[i][j];
            }
        }
    }

    long long answer = 0;

    for (int i = 0; i <= N; i++)
    {
        answer = max(answer, dp[N - 1][i]);
    }

    cout << answer;

    return 0;
}

풀이

전형적인 DP 문제

입력을 받고 DP[i][j]는 i열에 j번째까지 합이 최대가 되는 경로의 합이다

Bottom-to-Top 방법으로 DP 배열을 채워나가는데 라인 양 끝에 있는 숫자들을 예외 처리 해주고 나머지는 max를 통해 하면 된다

실버 1치고는 쉬운 문제