[백준] C++ 1932번 : 정수 삼각형

풀이과정

---

경로의 최대 합을 저장하는 배열(d)과 삼각형을 이루고 있는 배열(iValue)은 2차원 배열로 [y][x](y:높이,x:해당 층에서 몇번째인지)로 표현한다.

d[n][1]~d[n][n]은 삼각형의 마지막 층에서 각 요소(x가 1~n일 때)로 끝났을 때 최대값이 저장되어있다.

이들 중 가장 큰 값이 정수 삼각형에서 얻을 수 있는 최대값이다.

이 문제의 점화식은 d[n][m] = iValue[n] + max(d[n-1][m-1],d[n-1][m]) 이다.

 

코드

---

 

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int d[501][501] = { 0, };
	int iValue[501][501] = { 0, };

	int iInput = 0;

	cin >> iInput;

	cin >> iValue[1][1];

	d[1][1] = iValue[1][1];


	for (int i = 2; i <= iInput; ++i)
	{
		for (int j = 1; j <= i; ++j)
		{
			cin >> iValue[i][j];
			
			d[i][j] = iValue[i][j] + max(d[i - 1][j - 1], d[i - 1][j]);
		}
	}

	for (int i = 1; i <= iInput; ++i)
		d[iInput][0] = max(d[iInput][0], d[iInput][i]);
	
	cout << d[iInput][0] << endl;
	return 0;
}