[백준 / C++] 정수 삼각형(실버1, 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번째 줄까지 정수 삼각형이 주어진다.

출력

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

예제 입력 1

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

예제 출력 1

30

---

문제 풀이

이번 문제는 삼각형의 맨 위부터 시작하여 아래까지 내려오며 만나는 수들을 더해 가장 큰 수를 찾는 문제입니다.

아래층으로 내려올 때 대각선 왼쪽 / 오른쪽만을 선택할 수 있으며, 정수의 범위는 0 ~ 9999입니다.

 

문제의 예시는 삼각형으로 주어졌지만, 실제로 입력받아서 처리할 때는 2차원 배열로 입력받게 됩니다.

즉, 대각선 왼쪽 아래는 바로 아래(y + 1)를 의미하며, 대각선 오른쪽 아래는 바로 아래의 오른쪽 칸(y + 1, x + 1)을 의미합니다.

 

또한, 삼각형의 크기가 최대 500까지 가능하므로, 전체를 순회하며 모든 경우의 수를 따지는 방식으로는 해결할 수 없고 현재 칸에서의 최적의 해를 누적해가며 계산해야 합니다.

 

즉, DP[500][500]이라는 배열을 만들어 해당 칸의 최적의 해 [ "이전 칸(바로 위 or 대각선 왼쪽 위)의 최적의 해" + "현재 칸의 최적의 해" ]를 계산하여 저장하는 방식으로 접근하는 방식으로 문제를 해결하게 되었습니다.

 

이해가 안가신다면 RGB 거리 문제의 해설을 통해 그림으로 이해하셔도 좋습니다.

https://apth1023.tistory.com/140

[백준 / C++] RGB거리(실버1, 1149)

 

코드

#include <iostream>
#include <string.h>

using namespace std;

int n;
int arr[502][502];

int DP[502][502];

void Go(int num)
{
	if (num == n) return;

	// 다음 층
	for (int i = 0; i <= num; i++)
	{
		int rightIdx = i;
		int leftIdx = i - 1;

		int rightValue = -1;
		int leftValue = -1;

		// 오른쪽 위 칸이 존재하는 경우
		if (DP[num - 1][rightIdx] != -1)
		{
			rightValue = DP[num - 1][rightIdx];
		}

		// 왼쪽 위 칸이 존재하는 경우
		if (i - 1 >= 0)
		{
			leftValue = DP[num - 1][leftIdx];
		}

		DP[num][i] = max(rightValue, leftValue) + arr[num][i];
	}

	Go(num + 1);
}

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			int temp = 0;
			cin >> temp;

			arr[i][j] = temp;
		}
	}

	memset(DP, -1, sizeof(DP));

	DP[0][0] = arr[0][0];

	Go(1);

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

	cout << MaxValue;
}