DP - (1932) - 정수 삼각형.cpp

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 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

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

출력

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

---

삼각형을 2차원 배열로 생각했을 때

(i, j)에서 갈 수 있는 길은 바로 아래인(i-1, j) or 오른쪽 아래인 (i-1, j-1)이다.

/* dp 테이블
* 0 7 0 0 0 0 
* 0 3 8 0 0 0
* 0 8 1 0 0 0
* 0 2 7 4 4 0
* 0 4 5 2 6 5
* 형식으로 저장
*/

dp테이블을 다음과 같이 설정하고, i, j에 저장된 값 = 해당 위치를 밟을때까지의 가장 큰 값을 저장한다.

위에서는 i, j에서 아래로 내려갔지만 이번에는 (i, j)에서 내려가는 길이 아닌 위에서 받아오는 경우를 생각해보자.

그렇다면 i, j는 i-1, j와 i-1, j-1 중 하나를 선택할 수 있다.

다시 말해 위의 테이블에서 7은 3과 8 둘중 하나로 내려갈 수 있지만,

3은 0과 7중 하나를 받아 올 수 있고, 8은 7 과 0중 하나를 받아올 수 있다.

밑에 줄의 1을 보면 왼쪽 위의 3과 바로 위의 8 중 하나를 선택하는 것이다.

그렇다면 둘 중 누구를 선택하는게 이득인가? 큰 값을 만들어야 하니까 당연히 둘중 더 큰 값을 가져와 누적시키면 끝.

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

이러한 과정을 모두 거치면 dp 테이블의 맨 밑의 행은 여러 경로를 거친 후 가장 큰 값들이 있을 것이다.

해당 행을 for문으로 반복하여 가장 큰값만 찾아내면 끝.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 101;
const int INF = 987654321;
const int MOD = 1000000007;
int n;
int dp[502][502];
int len;
int main(void)
{
	cin >> n;
	/* dp 테이블
	* 0 7 0 0 0 0 
	* 0 3 8 0 0 0
	* 0 8 1 0 0 0
	* 0 2 7 4 4 0
	* 0 4 5 2 6 5
	* 형식으로 저장
	*/
	for (int i = 0; i <= n; i++) {
		for (int j = 1; j < i + 1; j++) {
			cin >> dp[i][j];
		}
	}
	/*
	* i, j는 바로 밑, 오른쪽 아래 2갈래의 길이 있다.
	* 즉 반대로 말하면 i, j는 왼쪽 위, 바로 위 둘중 더 큰 값을 선택하면 된다.
	*/
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j < i + 1; j++) {
			//더 큰 값 선택하여 값 누적시키기
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + dp[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		// 맨 밑층에는 여러 경로를 거친 후 가장 큰 값들이 있을 것이다.
		// 그 중 제일 큰것을 고르자.
		len = max(len, dp[n][i]);
	}
	cout << len;
}