[백준] 1932번 정수 삼각형

1932번: 정수 삼각형

RGB거리와 마찬가지로 

1번째부터 N번째까지 밑으로 내려가며 합이 최댓값이 되는 값만 저장한다.

문제에 있는 예제로 표현해보면

 

 

이렇게 최댓값인 30이 답이 되는 것이다.

 

이대로 구현해주면 끝

#include <iostream>
#include <algorithm>
using namespace std;
long long triangle[501][501] = { 0 };

int main() {
	int N;
	cin >> N >> triangle[0][0];

	for (int n = 1; n < N; n++) {
		for (int i = 0; i <= n; i++) {
			cin >> triangle[n][i];
			if (i == 0) triangle[n][i] += triangle[n - 1][i];
			else if (i == n) triangle[n][i] += triangle[n - 1][i - 1];
			else triangle[n][i] += max(triangle[n - 1][i], triangle[n - 1][i - 1]);
		}
	}

	long long Max = - 1;
	for (int i = 0; i <= N; i++) Max = max(Max, triangle[N - 1][i]);

	cout << Max;
	return 0;
}