[1932] 정수 삼각형

#include <iostream>
#define MAX 500
using namespace std;
int max(int a, int b);
int main()
{
	int testcase, i, j, sum;
	int dp[MAX][MAX];
	cin >> testcase;
	for (i = 0; i < testcase; i++)
	{
		for (j = 0; j <= i; j++)
			cin >> dp[i][j];
	}
	for (i = 1; i < testcase; i++)
	{
		for (j = 0; j <= i; j++)
		{
			if (j == 0)
				dp[i][j] += dp[i - 1][j];
			else if (j == i)
				dp[i][j] += dp[i - 1][j - 1];
			else
				dp[i][j] = max(dp[i-1][j-1], dp[i - 1][j]) + dp[i][j];
		}
	}
	sum = dp[testcase - 1][0];
	for (i = 1; i < testcase; i++)
	{
		if (sum < dp[testcase - 1][i])
			sum = dp[testcase - 1][i];
	}
	cout << sum << endl;
	return 0;
}
int max(int a, int b)
{
	return (a > b) ? a : b;
}