Algorithm/유형별 : DP

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

쟌쥰 2020. 2. 2. 13:30

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

 

1932번: 정수 삼각형

문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는

www.acmicpc.net

#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;
}