코딩테스트/백준
[실1] 1932 - 정수 삼각형
ShovelingLife
2022. 7. 5. 11:20
#include <iostream>
#include <algorithm>
using namespace std;
int arr[501][501]{ 0 };
int dp[501][501]{ 0 };
int main()
{
int n; cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
cin >> arr[i][j];
dp[1][1] = arr[1][1];
for (int i = 2; i <= n; i++)
for (int j = 1; j <= i; j++)
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + arr[i][j];
int res = 0;
for (int i = 1; i <= n; i++)
res = max(res, dp[n][i]);
cout << res << '\n';
return 0;
}