[C++] BOJ / 1932번 / 정수 삼각형

1932번: 정수 삼각형

 

문제

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

풀이

기본적으로 계산은 삼각형의 아래쪽부터 시작합니다.

가장 아래쪽에 있는 숫자들의 경우에는 왼쪽 또는 오른쪽 대각선에 더할 값이 없으므로 배제하고, 그 다음 층부터 계산하면 됩니다.

 

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

 

다음과 같이 되어 있을 때 밑에서 두 번째 층의 가장 첫 번째 원소로 올 수 있는 경우의 수는 (2 + 4) 또는 (2 + 5)가 됩니다. 이 중 최댓값은 2 + 5 = 7 이므로 최종적으로 7이 해당 공간에 위치하게 됩니다.

 

이와 마찬가지로 그 다음 원소인 7에 대해서도 최댓값을 구할 수 있으며, 이 과정을 계속 반복해가며 가장 위쪽의 원소까지 도달하게 되면 합이 최대가 되는 수의 합을 구할 수 있습니다.

 

제가 구한 점화식은 다음과 같습니다.

 

DP[i][j] = DP[i][j] + max(DP[i - 1][j], DP[i - 1][j + 1])

 

여기서 DP[i][j]란 i 번째 행에 있는 j 번째 원소의 값을 의미합니다.

참고로 저의 경우 삼각형의 가장 아래쪽에 있는 행을 첫 번째 행이라고 기준을 두었습니다.

---

#include <iostream>

using namespace std;

#define MAX 500
#define endl '\n'

int DP[MAX][MAX];

int main()
{
	int n;

	cin >> n;
	for (int i = n - 1; i > -1; --i)
		for (int j = 0; j < n - i; ++j)
			cin >> DP[i][j];

	for (int i = 1; i < n; ++i)
		for (int j = 0; j < n - i; ++j)
			DP[i][j] += max(DP[i - 1][j], DP[i - 1][j + 1]);

	cout << DP[n - 1][0] << endl;
}