[C++ / 백준 1392번] 정수 삼각형

 

 

 

2차원 배열로  해결했다.

 

 

 

#include <iostream>

using namespace std;

#define MOD 10007

int a[501][501];
int dp[501][501];

int main() {
    
    int N;
    
    cin >> N;

    for (int i = 1; i <= N ; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            int input;
            cin >> input;
            a[i][j] = input;
        }
    }

    int ans = a[1][1];

    dp[1][1] = a[1][1];
    for (int i = 2; i <= N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            if (j == 1)
            {
                dp[i][j] = dp[i - 1][j] + a[i][j];
            }
            else if (j == i)
            {

                dp[i][j] = dp[i - 1][j - 1] + a[i][j];
            }
            else
            {
                dp[i][j] = a[i][j] + max(dp[i - 1][j - 1], dp[i - 1][j]);
            }

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

    }

    cout << ans;

    

    

    return 0;
}