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

블로그에 올리는 모든 문제 풀이는 깃허브에 올려져 있습니다.

---

문제 설명

• 삼각형의 맨 위층부터 시작해서 아래에 있는 수 중 하나를 선택하여 내려올때, 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하시오.
  (현재 층에서 선택 된 수의 왼/오른쪽 아래 대각선만 선택 할 수 있다.)
• 첫째 줄에 삼각형의 크기(1<=n<=500), 둘째 줄부터 n+1번째 줄까지 정수(0<=x<=9999) 삼각형이 주어진다.

---

풀이 전략

• 삼각형의 규칙을 구한다.
  

  

  • dp[0][0] = 7
    dp[1][0] = 3+7, dp[1][1] = 8+7
    dp[2][0] = 8+dp[1][0], dp[2][1] = 1+max(dp[1][0],dp[1][1]), dp[2][2] = 0+dp[1][1]
    dp[3][0] = 2+dp[2][0], dp[3][1] = 7+max(dp[2][0],dp[2][1]), dp[3][2] = 4+max(dp[2][1],dp[2][2]), dp[3][3] = 4+dp[2][2]
    .......
  • 양 사이드는 본인 + 위의 값, 중간은 본인 + 양 대각선 위쪽값 중 큰 값 임을 알 수 있다.

소스 코드

#include <iostream>
#include <algorithm>

int dp[500][500] = { 0, };

using namespace std;
int main()
{
	int n, maxNumber = 0;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			cin >> dp[i][j];
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			if (j == 0)
				dp[i][j] = dp[i - 1][0] + dp[i][j];
			else if (i == j)
				dp[i][j] = dp[i - 1][j - 1] + dp[i][j];
			else
				dp[i][j] = max(dp[i - 1][j - 1] + dp[i][j], dp[i - 1][j] + dp[i][j]);

			maxNumber = max(maxNumber, dp[i][j]);
		}
	}

	cout << maxNumber;
}

---

링크

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

1932번: 정수 삼각형