[백준 C++] 1932 정수 삼각형 - 다이나믹프로그래밍

1932번: 정수 삼각형

#include <iostream>
using namespace std;

int Triangle[501][501];
int DP[501][501];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;

	cin >> Triangle[1][1];
	DP[1][1] = Triangle[1][1];

	int Max = DP[1][1];

	for (int i = 2; i <= N; ++i)
	{
		for (int j = 1; j <= i; ++j)
		{
			cin >> Triangle[i][j];

			if (j == 1)
			{
				DP[i][j] = DP[i - 1][j] + Triangle[i][j];
			}
			else if (j == i)
			{
				DP[i][j] = DP[i - 1][j - 1] + Triangle[i][j];
			}
			else
			{
				DP[i][j] = max(DP[i - 1][j - 1], DP[i - 1][j]) + Triangle[i][j];
			}

			if (i == N && DP[i][j] > Max)
			{
				Max = DP[i][j];
			}
		}
	}
	
	cout << Max;
}

---

 

다이나믹 프로그래밍 유형의 문제입니다.

맨 위층을 1층이라고 했을 때 2층 부터 일반화된 점화식을 이용해서 DP 배열 값을 저장해줄 수 있습니다.

각 층의 맨 왼쪽 원소 또는 맨 오른쪽 원소를 제외한 나머지 원소의 DP 점화식은 다음과 같이 일반화할 수 있습니다.

 

(1,1) 원소부터 (i, j) 원소를 경유할 때까지 최대값: DP[i][j] = max(DP[i - 1][j - 1], DP[i - 1][j]) + Triangle[i][j]

 

각 층의 맨 왼쪽 원소 또는 맨 오른쪽 원소는 위층에서 내려오는 원소의 경우가 한 가지 밖에 없기 때문에

DP[i][j] = DP[i - 1][j] + Triangle[i][j]

DP[i][j] = DP[i - 1][j - 1] + Triangle[i][j]

와 같이 표현할 수 있습니다.