1932. 정수 삼각형

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

1932번: 정수 삼각형

TOP-DOWN 방식을 이용하는 DP 문제이며, DP 배열에 자기 자신의 상태를 저장한다.

삼각형의 맨 위 꼭지점부터 아래로 내려올때 각 지점에서 최대값을 저장하며 마지막까지 내려간다.

마지막에 도달하면 그 중에서 최대값을 골라내면 된다.

 

 

그림에 나타낸것과 똑같이 1,2~N-1,N 의 세가지 경우에 대해 점화식을 세워서 해결하였다.

N번째의 첫번째 원소의 경우, dp[n][0] = dp[n - 1][0] + 자기자신의 값

N번째의 2~N-1번째 원소의 경우, dp[n][j] = max(dp[n][j - 1], dp[n][j]) + 자기자신의 값.

N번째의 N번째 원소의 경우, dp[n][n] = dp[n - 1][n - 1] + 자기자신의 값

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include<vector>
#include<algorithm>
#include <cstring>
#include<list>
#include<cmath>
#include<stack>
using namespace std;
int tr[501][501];
int dp[501][501] = { 0, };
vector <int> p;
int ans = 0;
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {		
		for (int j = 0; j <=i; j++) {
			cin >> tr[i][j];
		}
	}

	
	
	for (int i = 0; i < n; i++) {
		if (n == 1) {
			dp[0][0] = tr[0][0];
			ans = dp[0][0];
			break;
		}

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

	cout << ans;
	
	
	

}