[class4] (백준 1932) 정수 삼각형

문제

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

제한

 

예제 입력 1

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

예제 출력 1

30

힌트

 

W3sicHJvYmxlbV9pZCI6IjE5MzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTVcdWMyMTggXHVjMGJjXHVhYzAxXHVkNjE1IiwiZGVzY3JpcHRpb24iOiI8cHJlPlxyXG4gICAgICAgIDdcclxuICAgICAgMyAgIDhcclxuICAgIDggICAxICAgMFxyXG4gIDIgICA3ICAgNCAgIDRcclxuNCAgIDUgICAyICAgNiAgIDU8XC9wcmU+XHJcblxyXG48cD5cdWM3MDQgXHVhZGY4XHViOWJjXHVjNzQwIFx1ZDA2Y1x1YWUzMFx1YWMwMCA1XHVjNzc4IFx1YzgxNVx1YzIxOCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVkNTVjIFx1YmFhOFx1YzJiNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWU4IFx1YzcwNFx1Y2UzNSA3XHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MVx1ZDU3NFx1YzExYyBcdWM1NDRcdWI3OThcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIxOCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YzVlYyBcdWM1NDRcdWI3OThcdWNlMzVcdWM3M2NcdWI4NWMgXHViMGI0XHViODI0XHVjNjJjIFx1YjU0YywgXHVjNzc0XHVjODFjXHVhZTRjXHVjOWMwIFx1YzEyMFx1ZDBkZFx1YjQxYyBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MThcdWIyOTQgXHVhY2JkXHViODVjXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHViNzdjLiBcdWM1NDRcdWI3OThcdWNlMzVcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIxOFx1YjI5NCBcdWQ2MDRcdWM3YWMgXHVjZTM1XHVjNWQwXHVjMTFjIFx1YzEyMFx1ZDBkZFx1YjQxYyBcdWMyMThcdWM3NTggXHViMzAwXHVhYzAxXHVjMTIwIFx1YzY3Y1x1Y2FiZCBcdWI2MTBcdWIyOTQgXHViMzAwXHVhYzAxXHVjMTIwIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhYzgzIFx1YzkxMVx1YzVkMFx1YzExY1x1YjljYyBcdWMxMjBcdWQwZGRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCAxIFx1Yzc3NFx1YzBjMSA1MDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LiBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjNzc0XHViOGU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWFjMDEgXHVjMjE4XHViMjk0IFx1YmFhOFx1YjQ1MCBcdWM4MTVcdWMyMThcdWM3NzRcdWJhNzAsIFx1YmM5NFx1YzcwNFx1YjI5NCAwIFx1Yzc3NFx1YzBjMSA5OTk5IFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1ZDA2Y1x1YWUzMCBuKDEgJmxlOyBuICZsZTsgNTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgbisxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWM4MTVcdWMyMTggXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwJm5ic3A7XHVkNTY5XHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MThcdWIyOTQgXHVhY2JkXHViODVjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxOTMyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIFRyaWFuZ2xlIiwiZGVzY3JpcHRpb24iOiI8cHJlPlxyXG4gICAgICAgIDdcclxuICAgICAgMyAgIDhcclxuICAgIDggICAxICAgMFxyXG4gIDIgICA3ICAgNCAgIDRcclxuNCAgIDUgICAyICAgNiAgIDUgKEZpZ3VyZSAxKTxcL3ByZT5cclxuXHJcbjxwPkZpZ3VyZSAxIHNob3dzIGEgbnVtYmVyIHRyaWFuZ2xlLiBXcml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSBoaWdoZXN0IHN1bSBvZiBudW1iZXJzIHBhc3NlZCBvbiBhIHJvdXRlIHRoYXQgc3RhcnRzIGF0IHRoZSB0b3AgYW5kIGVuZHMgc29tZXdoZXJlIG9uIHRoZSBiYXNlLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkVhY2ggc3RlcCBjYW4gZ28gZWl0aGVyIGRpYWdvbmFsbHkgZG93biB0byB0aGUgbGVmdCBvciBkaWFnb25hbGx5IGRvd24gdG8gdGhlIHJpZ2h0LjxcL2xpPlxyXG5cdDxsaT5UaGUgbnVtYmVyIG9mIHJvd3MgaW4gdGhlIHRyaWFuZ2xlIGlzICZnZTsgMSBidXQgJmxlOyA1MDAuPFwvbGk+XHJcblx0PGxpPlRoZSBudW1iZXJzIGluIHRoZSB0cmlhbmdsZSwgYWxsIGludGVnZXJzLCBhcmUgYmV0d2VlbiAwIGFuZCA5OTk5IChpbmNsdXNpdmUpLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5EYXRhIGFib3V0IHRoZSBudW1iZXIgb2Ygcm93cyBpbiB0aGUgdHJpYW5nbGUgYXJlIGZpcnN0IHJlYWQgZnJvbSB0aGUgaW5wdXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGhpZ2hlc3Qgc3VtIGlzIHdyaXR0ZW4gYXMgYW4gaW50ZWdlciBpbiB0aGUgb3V0cHV0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

#include <iostream> 
using namespace std;
int triangle[500][500];
int sum[500][500];
int getResult(int num,int index)
{
	if (num == 0)
	{
		return triangle[0][0];
	}

	if (sum[num][index] == -1)
	{
		if (index == 0)
		{
			sum[num][index] = getResult(num-1, index) + triangle[num][index];
		}
		else if (index == num)
		{
			sum[num][index] = getResult(num - 1, index - 1) + triangle[num][index];
		}
		else
		{
			int a = getResult(num - 1, index - 1) + triangle[num][index];
			int b = getResult(num - 1, index) + triangle[num][index];
			sum[num][index] = (a > b) ? a : b;
		}
	}

	return sum[num][index];
}
int main() 
{ 
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			cin >> triangle[i][j];
			sum[i][j] = -1;
		}
	}

	int max = 0;
	for (int i = 0; i < N; i++)
	{
		int temp = getResult(N - 1, i);
		max = max < temp ? temp : max;
	}

	cout << max;
	return 0;
}