[백준/C++] 1932번 : 정수 삼각형 (DP 연습)

정수 삼각형 

문제

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

예제 입력 1

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

예제 출력 1

30

---

DP 문제를 풀기 위해서 가장 핵심인 규칙을 찾아야 한다.

 

 dp[0][0] = 7
 dp[1][0] = 7+3 dp[1][1] = 7+8
 dp[2][0] = 7+3+8 dp[2][1] = max(dp[1][0],dp[1][1]) dp[2][2] = 7+8+0

...

 

이처럼, 삼각형의 가장 왼쪽 또는 가장 오른쪽 끝 라인은 바로 윗 부모의 값을 그대로 받아 더한다.

반면 가장자리가 아닌 가운데 자리는 왼쪽 위 / 오른쪽 위 부모 중 더 큰 값을 갖는 원소를 찾아 더해야 한다.

부모의 index는 [i - 1]로 행은 같고, [ j ] 또는 [j - 0] 으로 왼쪽 또는 바로 위에 존재한다.

 

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

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

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

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

	/*
	 dp[0][0] = 7
	 dp[1][0] = 7+3		dp[1][1] = 7+8
	 dp[2][0] = 7+3+8	dp[2][1] = max(0,1)	dp[2][2] = 7+8+0
	 */
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			if (j == 0)
				dp[i][j] = dp[i - 1][j] + tri[i][j];
			else if (i == j)
				dp[i][j] = dp[i - 1][j - 1] + tri[i][j];
			else
				dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + tri[i][j];
		}
	}

	int maxDP = dp[n - 1][0];
	for(int i = 1; i < n; i++)
		maxDP = max(maxDP, dp[n - 1][i]);

	cout << maxDP;

	return 0;
}

 

마지막 최종 값은 주어진 삼각형의 크기 행에 존재하는 DP값 중 가장 큰 값을 찾아 출력하며 된다.

 

다 풀이하고 나니 생각보다 쉬운 문제처럼 보이고 풀이가 너무 명확했다.

풀이하는 과정에서는 삼각형의 가장자리와, 가운데 자리의 차이점을 찾기까지가 꽤나 오래걸렸다. 

단순히 부모의 값 중 더 큰 값을 찾아야 한다고 생각하고 점화식을 세우다가 마침내 규칙을 찾았다.

---

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형