정수 삼각형 (백준 - 1932번)

동적계획법을 사용하는 문제이다. 

 

아래 층에 있는 수를 선택 할때에는 대각선 왼쪽과 오른쪽 중 하나만 선택이 가능하다는 조건을 상기하며 살펴보도록 하자.

 

층마다 저장해야 할 정수 값들이 늘어난다. 그렇기 때문에 값을 저장할때나 DP테이블로 사용할때 2차원 배열이 필요하다. 

 

맨 위에 값은 하나이기 때문에 DP테이블에 맨 윗층은 한개의 값이 저장된다. 그리고 2층은 값이두개가 되며 맨 위층의 값과 더하여 DP 테이블에 2개의 값이 저장된다. 여기서 특성을 알수 있는데 양 사이드에 있는 값들은 무조건 왼쪽 값은 그 위층의 맨 왼쪽값과만 더할 수 있고, 오른쪽 값은 그 위층의 맨 오른쪽 값과만 더할 수 있다. 

 

그리고 3층은 값이 세개가 되며 양 사이드 2개의 값은 위와 같은 규칙으로 더해지고, 중간 값 하나는 2층의 두 값중 가장 큰 값과 더해져 DP 테이블에 3개의 값이 저장된다. 여기서 또 특성이 나오는데 중간에 있는 값들은 무조건 그 위층의 바로 왼쪽과 오른쪽 값 중 가장 큰 값과 더해진다.  

 

예를들어 M층에서 맨 왼쪽 값의 인덱스는 0이며 맨 오른쪽 값의 인덱스는 N이라고 하자. 규칙을 정리해보면 다음과 같다. (DP 2차원 배열은 DP테이블이며 S 2차원 배열은 삼각형정수값을 저장하는 배열이다..)

 

• (가장 왼쪽값인 경우) DP[M][0] = DP[M - 1][0] + S[M][0]
  
  
• (중간 값인 경우) DP[M][중간] = DP[M - 1][중간], DP[M-1][중간 + 1] 둘중 큰값 + S[M][중간]
• (가장 오른쪽값인 경우) DP[M][N] = DP[M - 1][N - 1]
  (전 층 M - 1의 정수의 갯수는 M층의 갯수보다 1적으므로 N - 1가 가장 오른쪽 값이다.)

이 규칙으로 원하는 끝 층까지 계산한 후 DP 테이블에서 끝 층에 기록된 값들 중 가장 큰 값을 출력하면 그것이 선택된 수의 합중 가장 최대가 된다.

 

코드는 다음과 같다.

#include <iostream>
#include <string.h>
using namespace std;

int tri[501][501];
int dp[501][501];

int max(int a, int b)
{
	return a > b ? a : b;
}

int main()
{
	int input;
	cin >> input;

	for (int i = 0; i < input; ++i)
	{
		for (int j = 0; j <= i; ++j)
		{
			cin >> tri[i][j];
		}
	}

	int result = 0;
	dp[0][0] = tri[0][0];
	for (int i = 1; i < input; ++i)
	{
		for (int j = 0; j <= i; ++j)
		{
			if (j == 0)
				dp[i][j] = dp[i - 1][j] + tri[i][j];
			else if (j == i)
				dp[i][j] = dp[i - 1][j - 1] + tri[i][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + tri[i][j];

			// 마지막 줄의 값들 중 최대값
			if (i == (input - 1))
			{
				if (result < dp[i][j])
					result = dp[i][j];
			}
		}
	}

	cout << result << endl;
}