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

1932번: 정수 삼각형

 

 

DP만 부시는 중....

비슷한 유형 계속 풀다보니 확실히 감이 생기는 것 같다. 

 

 

이 문제의 경우 점화식을 

D[n][i] = 크기 n의 정수 삼각형에서 i번째 요소를 마지막으로 선택했을 때의 최대 경로합

으로 정의하면, 

 

D[n][i] = max(D[n-1][i-1], D[n-1][i]) + a[n][i]  (i != 1 && i != n)

D[n][i] = D[n-1][i] + a[n][i]  (i == 1)

D[n][i] = D[n-1][i-1] + a[n][i] (i == n)

 

이 된다. 

 

이를 코드로 옮기면 다음과 같다. 

 

#include <iostream>

int d[501][501];
int a[501][501];

int dp(int n, int i)
{
	if (d[n][i] != -1) return d[n][i];

	if (n == 1) return a[1][1];

	if (i == 1) d[n][i] = dp(n - 1, i);
	else if (i == n) d[n][i] = dp(n - 1, i - 1);
	else
	{
		d[n][i] = dp(n - 1, i - 1);
		if (d[n][i] < dp(n - 1, i)) d[n][i] = dp(n - 1, i);
	}

	d[n][i] += a[n][i];
	return d[n][i];
}

int main()
{
	int n;
	std::cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
			d[i][j] = -1;
	}
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= i; ++j)
			std::cin >> a[i][j];
	}
	
	int result = 0;
	for (int i = 1; i <= n; ++i)
	{
		if (result < dp(n, i)) result = dp(n, i);
	}
	std::cout << result;
}