[BOJ 1932] 정수 삼각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

---

문제에서는 삼각형이 예각 삼각형처럼 보이지만, 입력을 보면 직각삼각형 형태이다.

 

이를 통해서 보면 i번째 줄에는 (i + 1)개의 입력을 받는다. ( i가 0부터 시작할 때)

 

i행 j열까지의 합 중 가장 큰 값을 F(i, j)라고 하고 i행 j열의 값을 a(i, j)라고 할 때

 

F(i + 1, j) = max{F(i + 1, j), F(i, j) + a(i + 1, j), F(i, j - 1) + a(i + 1, j)} 이다. 

 

즉, F(i + 1, j)는 그 위의 행에서 대각선에 있는 두 F(i, j), F(i, j - 1)의 값에 a(i + 1, j)를 더한 값 중 가장 큰 값이다.

 

이것을 코드로 편하게 구현하면 반복문을 돌면서 (i, j)에서 (i + 1, j), (i + 1, j + 1)의 값을 차례로 결정하면 된다.

---

#include <stdio.h>

#define max(a,b) (a) > (b) ? (a): (b)

int dp[501][501];
int a[501][501];
int main()
{
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < i + 1; j++)
		{
			scanf("%d", &a[i][j]);
		}
	}
	dp[0][0] = a[0][0];
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < i + 1; j++)
		{
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a[i + 1][j]);
			dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + a[i + 1][j + 1]);
		}
	}

	int max = 0;
	for (int i = 0; i < n; i++)
	{
		if (max < dp[n - 1][i])
			max = dp[n - 1][i];
	}

	printf("%d", max);
	return 0;
}