BOJ 백준 1932 정수 삼각형 <DP>

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

< 정수 삼각형 >

        7                        7
      3   8                   10   15
    8   1   0       ->      18   16   15
  2   7   4   4           20   25  20   19
4   5   2   6   5       24   30   27  26   24

< 삼각형 배열 >                    < dp 배열 >

 삼각형의 크기 n이 주어지고 삼각형의 안의 숫자가 주어진 뒤에 계단을 타고 내려오듯이 수들을 골랐을 때 그 합이 가장 큰 경우를 출력하면 된다.

위의 예시를 보면 크기 n은 5로 주어졌고 위에서부터 5줄 내려오면서 1씩 증가하면서 수가 입력되는 것을 알 수 있다.

위의 답은

7 -> 3 -> 8 -> 7 -> 5 로 30이 최대이고 이를 출력해주면 된다.

평범한 dp문제를 풀듯이, 각 줄에 내려오면서 그 줄의 최댓값들을 dp배열에 적어주면 된다.

점화식은 아래와 같이 설정해서 풀었다.

k = 0 to 1

dp[i + 1][j + k] = dp[i][j] + arr[i + 1][j + k] > dp[i + 1][j + k] ? dp[i][j] + arr[i + 1][j + k] : dp[i + 1][j + k]

삼각형 크기가 n이라면, n-1줄까지만 돌려주면서 자신의 아랫줄에 연결된 두 수의 최댓값들을 갱신해주는 형태이다.

#include <iostream>
#include <vector>
#include <memory.h>
#define SIZE 501

using namespace std;

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

	int n;
	cin >> n;

	vector<int> v[SIZE];
	int dp[SIZE][SIZE];
	memset(dp, 0, sizeof(dp));
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < i + 1; ++j)
		{
			int x; cin >> x;
			v[i].push_back(x);
		}
	}
	
	dp[0][0] = v[0][0];
	for (int i = 0; i < n - 1; ++i)
	{
		for (int j = 0; j < v[i].size(); ++j)
		{
			for (int k = 0; k < 2; ++k)
			{
				dp[i + 1][j + k] = dp[i][j] + v[i + 1][j + k] > dp[i + 1][j + k] ? dp[i][j] + v[i + 1][j + k] : dp[i + 1][j + k];
			}
		}
	}
	int iMax = -1;
	for (int i = 0; i < n; ++i)
	{
		if (dp[n - 1][i] > iMax)
			iMax = dp[n - 1][i];
	}
	cout << iMax << '\n';

	return 0;
}