[BOJ] 1932 정수 삼각형 - 동적 계획법

매우 간단한 문제이다. 

아래층으로 값을 더하고, 거기 기록한다. 

어떠한 인덱스에서 갈수있는 아래층 원소의 인덱스를 구하기 위해서는

현재 인덱스와 내가 속한 레이어의 번호를 더해주면 쉽게 구할수 있다.

인덱스 2는 4와 5로 접근 가능하고, 인덱스 3도 5에 접근 가능하다.

자연스럽게 최대값이 구해진다.

 

 

레이어를 하나씩 증가시키면서 원소 개수만큼 루프를 돌리며

바로 다음 레이어의 최대값을 계속 구해주다 보면 원하는 값을 구할 수 있다.

코드로 구현한 결과는 다음과 같다.

 

#include <iostream>
 
int MaxResult[125251] = { 0 , };
int Cost[125251] = { 0 , };
 
int main()
{
	std::cin.tie(0);
	std::cin.sync_with_stdio(false);
	std::cout.sync_with_stdio(false);
 
	int N = 0;
	std::cin >> N;
 
	int Cin = 1;
 
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= i; ++j)
			std::cin >> Cost[Cin++];
	}
	
	int LayerStart = 1;
	MaxResult[1] = Cost[1];
 
	for (int CurrentLayer = 1; CurrentLayer < N; ++CurrentLayer)
	{	
		int CurrentNumber = LayerStart;
		for (int k = CurrentNumber; k < CurrentNumber + CurrentLayer; ++k)
		{
			if (MaxResult[k + CurrentLayer] < MaxResult[k] + Cost[k + CurrentLayer])
				MaxResult[k + CurrentLayer] = MaxResult[k] + Cost[k + CurrentLayer];
 
			if (MaxResult[k + CurrentLayer + 1] < MaxResult[k] + Cost[k + CurrentLayer + 1])
				MaxResult[k + CurrentLayer + 1] = MaxResult[k] + Cost[k + CurrentLayer + 1];
		}
		LayerStart = LayerStart + CurrentLayer;
	}
 
	int Max = -1;
	for (int i = LayerStart; i < LayerStart + N; ++i)
	{
		if (MaxResult[i] > Max)
			Max = MaxResult[i];
	}
	std::cout << Max << std::endl;
 
	return 0;
}