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

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

1932번: 정수 삼각형

#include<iostream>
using namespace std;

#define MAX(X, Y) ((X) > (Y) ? (X) : (Y))

int main(void) {
	int n, answer = 0;
	cin >> n;

	//2차원배열 동적할당
	int **mat;
	mat = new int*[n];

	for (int i = 0; i < n; i++) 
		mat[i] = new int[i+1];

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


	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < i + 1; j++) {

			if (j == 0)
				mat[i][j] = mat[i - 1][j] + mat[i][j];
			else if (j == i)
				mat[i][j] = mat[i - 1][j - 1] + mat[i][j];
			else
				mat[i][j] = MAX(mat[i - 1][j - 1] + mat[i][j], mat[i - 1][j] + mat[i][j]);
		
			if (answer < mat[i][j])
				answer = mat[i][j];
		}

	}

	cout << answer << endl;
}