[알고리즘] 정수 삼각형 - 백준 1932

문제

 

해결

전에 풀었던 RGB거리 문제의 해결 방법과 같은 방법으로 접근해야 할 것 같다.

하나의 경로만 선택하여 탐색을 진행한다면 이후 선택들에 제한이 생기게 되고 그 제한을 모두 고려하여 최적의 경로를 찾는 것은 불가능 하다고 생각된다. 때문에 모든 경로를 지나가는 방법으로 문제를 해결해야 한다.

이렇게 되면 로직은 간단해진다. 

 

1. 현재 경로로 오는 가장 큰 비용을 선택한다. 
2. 선택한 비용에 현재 경로의 비용을 더한다. 
3. 이 과정을 1층에 도착할 때 까지 반복한다. 

이러한 과정을 지나면 마지막 n개의 비용들 중 1층에 내려오는 것에 대한 최대 비용이 저장되므로 그 값들 중에서 가장 큰 수를 선택하면 문제 해결이다. 

 

이제 현재 경로로 오는 가장 큰 비용을 구하는 식을 생각해야 한다.

 

숫자들을 2차원 배열로 저장하면 쉽게 구할 수 있을 것 같다.

	0	1	2
0	0 0
1	1 0	1 1
2	2 0	2 1	2 2

인덱스를 나타내면 이렇다. 

이대로 점화식을 구하면 

 

maxCost[i][j] = maxCost[i - 1][j] + cost[i][j];

열이 0인 경우

 

maxCost[i][j] = maxCost[i - 1][j - 1] + cost[i][j];

열이 행과 같을 경우

 

maxCost[i][j] = max(minCost[i - 1][j - 1] + cost[i][j], maxCost[i - 1][j] + cost[i][j]);

그 외

 

 

코드

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

int cost[500][500], maxCost[500][500];
int n, result = 0;

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			int num;

			cin >> num;

			cost[i][j] = num;
		}
	}

	maxCost[0][0] = cost[0][0];
	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			if(j == 0)
				maxCost[i][j] = maxCost[i - 1][j] + cost[i][j];
			else if(j == i)
				maxCost[i][j] = maxCost[i - 1][j - 1] + cost[i][j];
			else
				maxCost[i][j] = max(maxCost[i - 1][j - 1] + cost[i][j], maxCost[i - 1][j] + cost[i][j]);
		}
	}

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

	cout << result;
}