[BOJ][DP] 1932. 숫자삼각형

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

DP 문제다. 

문제에서 우리가 잡아내야 할 포인트는 

1. 이제까지 선택된 수의 합이 최대가 되는 경로.

2. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼/오 중 하나를 선택.

점화식을 세우기 위해서 일단 이해를 해보자.

문제에서는 수들을 삼각형의 형태로 나타내었지만, 

어렵게 생각할 필요가 없다.

위에서부터 차례대로 배열에 넣어주면 아래와 같다.

그럼 여기서 어떻게 어떠한 값에 대한 왼/오 대각선 값을 가리킬 수 있을까?

보다시피 한 값의 인덱스 +2 = L, +3 = R 이 되는것을 알 수있다.

얼추 이해가 오기 시작하는가?

그렇다면 이제 여태까지 이해한 것을 바탕으로 점화식을 세워보자.

(arr은 입력받았던 값을 저장해둔 배열이다.)

L 대각선 : DP[index + 층수] = arr[index + 층수] + DP[index]

R 대각선 : DP[index + 층수 + 1] = arr[index + 층수 + 1] + DP[index]

(index는 차례대로 배열을 가리켜주기 위한 변수이다.)

여기서 주의해야 할 점은, index의 R 대각선 값과 index+1 L 대각선 값이 놓여지는 위치가 같아진다.

우리는 최대값을 저장하는 것이므로 대소비교를 하여 더 큰수를 넣어준다.

- Source - 

	//================================================
	// Filename : 1932_NumTriangle
	//
	// Solved by PSDent.
	//
	// https://www.acmicpc.net/problem/1932
	//================================================
	#include <iostream>
	short N;
	long long DP[251001], arr[251001], max;
	void Bigger(long long a) {
	max = max < a ? a : max;
	return;
	}
	void Calculate()
	{
	int index = 0;
	DP[0] = arr[0];
	for (int i = 1; i <= N; i++)
	{
	for (int j = 0; j < i; j++)
	{
	if (arr[index + i] + DP[index] > DP[index + i])
	DP[index + i] = arr[index + i] + DP[index];
	if (arr[index + i + 1] + DP[index] > DP[index + i + 1])
	DP[index + i + 1] = arr[index + i + 1] + DP[index];
	index++;
	}
	}
	return;
	}
	int main()
	{
	int t = 0;
	std::cin >> N;
	for (int i = 1; i <= N; i++) t += i;
	for (int i = 0; i < t; i++) std::cin >> arr[i];
	Calculate();
	for (int i = t - N - 1; i < t; i++)
	Bigger(DP[i]);
	std::cout << max;
	return 0;
	}