[DP] BOJ 1932번 정수 삼각형

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

1932번: 정수 삼각형

- 문제 파악

정수 N이 주어지고 크기가 N인 삼각형이 주어진다 이 중에서 수를 선택할 수 있는데 선택한 수의 다음 줄의 왼쪽 또는 오른쪽만 선택할 수 있다. 이렇게 선택한 수들의 합의 최대값을 출력하라

 

- 정답

무식하게 요소에 접근 할때마다 이전까지 더했던 값의 합과 현재 요소를 더했을 때 큰 값을 남기도록 했다.

시간제한 2초 정도면 이중for문으로 무식하게 풀어도 되나보다.

 

#include "bits/stdc++.h"

using namespace std;

int n;
unsigned long long arr[502][502];
unsigned long long D[502][502];
unsigned long long ans;

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

	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			cin>> arr[i][j];
		}
	}

	D[1][0] = arr[1][1];
	D[1][1] = arr[1][1];
	int nPos = 1;

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

			

		}
	}

	for (int i = 1; i <= n; i++)
	{
		ans = max(D[n][i], ans);
	}


	cout << ans;

}