14. TRIANGLEPATH

알고라파덕.

14. TRIANGLEPATH 소스.

#include <stdio.h>

void TRIANGLEPATH();
int main()
{
	int testcase;
	scanf("%d", &testcase);
	while(testcase >= 1)
	{
		--testcase;
		TRIANGLEPATH();
	}
	return 0;
}
void TRIANGLEPATH()
{
	int data[105][105] = { 0};
	int sum[105][105] = { 0 };
	int N, i, j, max = 0;
	scanf("%d", &N);
	for(i=1; i<=N; i++)
		for(j=1; j<=i; j++)
			scanf("%d", &data[i][j]);

	sum[1][1] = data[1][1];

	for(i=2; i<=N; i++)
	{
		for(j=1; j<=i; j++)
		{
			if(sum[i-1][j-1] > sum[i-1][j]) max = sum[i-1][j-1];
			else max = sum[i-1][j];

			sum[i][j] = max + data[i][j];
		}
	}
	max = 0;
	for(i=1; i<=N; i++)
	{
		if(max < sum[N][i]) max = sum[N][i];
	}
	printf("%d\n", max);
}