[백준 1932: 정수 삼각형] - C++

acmicpc.net/problem/1932

1932번: 정수 삼각형

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

int main()
{
	int n = 0;
	cin >> n;
	vector<int> info[500];
	int dp[500][500];
	int input;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < i + 1; j++)
		{
			cin >> input;
			info[i].push_back(input);
		}
	}
	dp[0][0] = info[0][0];
	int result = dp[0][0];

	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			int curInfo = info[i][j];
			if (j == 0) //제일 왼쪽일때 
			{
				dp[i][j] = dp[i - 1][j] + curInfo;
			}
			else if (j == i) //제일 오른쪽일때
			{
				dp[i][j] = dp[i - 1][j-1] + curInfo;
			}
			else 
			{
				dp[i][j] = max(dp[i - 1][j - 1],dp[i-1][j]) + curInfo;
			}

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

	cout << result << endl;
	return 0;
}