백준 1932 : 정수 삼각형

1. 문제 : https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

2. 문제 접근

• 완전 탐색 : 주어진 이진 트리의 높이는 $N$이고 경로의 수는 $2^{N-1}$이므로 모든 노드를 탐색한다면 시간이든 메모리든 모두 초과하게 된다.
• DP : 방문했던 노드를 중복해서 계속 방문하기 때문에 중복되는 Sub-Tree가 너무 많아 불필요한 계산을 하게 된다. 방문한 노드까지의 값을 미리 저장한다면 중복 방문하는 노드를 제거하여 많은 메모리와 시간을 아낄 수 있다. (메모이제이션)

 

3. 문제 해결

1. 모든 노드까지의 경로 합을 0으로 초기화한다.
2. 모든 노드를 순차적으로 순회하면서 해당 노드까지의 경로 합을 저장한다.
3. 가장 왼쪽, 오른쪽에 존재하는 노드는 자신의 부모 노드까지의 합에 자신의 값을 더한다.
4. 가운데에 존재하는 노드는 자신의 부모 노드가 두 개이므로 둘 중 값이 큰 부모를 선택하여 자신의 값을 더한다.
5. 모든 노드의 계산이 완료한 이후, 리프노드를 순회하면서 가장 큰 값을 반환한다.

IF I = 0 or I = K - 1, DP[K][I] += DP[K - 1][I]
ELSE, DP[K][I] += max(DP[K - 1][I - 1], DP[K - 1][I])

 

4. 코드

#include <iostream>
#include <vector>
using namespace std;

int solution(int N, vector<vector<int>>& tree)
{
	vector<vector<int>> dp;

	// Initialize the dp tree
	dp.push_back({ tree[0][0] });

	// Calculate the dp tree
	for (int i = 1; i < N; i++)
	{
		vector<int> temp;

		// The leftmost element
		temp.push_back(dp[i - 1][0] + tree[i][0]);
		// The elements positioned in the middle
		for (int j = 1; j < i; j++)
		{
			temp.push_back(max(dp[i - 1][j - 1], dp[i - 1][j]) + tree[i][j]);
		}
		// The rightmost element
		temp.push_back(dp[i - 1][i - 1] + tree[i][i]);

		dp.push_back(temp);
	}

	// Find the max value of the path
	int max = 0;
	for (int i = 0; i < N; i++)
	{
		if (dp[N - 1][i] > max)
		{
			max = dp[N - 1][i];
		}
	}

	return max;
}

int main()
{
	int N;
	vector<vector<int>> tree;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		vector<int> temp;

		for (int j = 0; j <= i; j++)
		{
			int value;
			cin >> value;
			temp.push_back(value);
		}

		tree.push_back(temp);
	}

	cout << solution(N, tree);

	return 0;
}