🖊️ 문제

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

---

🖊️ 풀이

사실 이거 프로그래머스에서 풀었다

그치만..
푼지 어언 50일
그래서 다시 마주친 김에 풀었는데
점화식은 바로 기억났고,
그러니까 바로 풀었다.

주석쳐놓은게 점화식이다.

2차원배열로 생각하고,
각 칸에 대해, 그 때 그 칸에서 가능한 합들의 최댓값을 저장해놓았다.

#include <iostream>
using namespace std;

int arr[501][501];
int dp[501][501];

int main()
{
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cin >> arr[i][j];
		}
	}

	//dp[1][1] = arr[1][1];

	//dp[2][1] = arr[2][1] + arr[1][1];
	//dp[2][2] = arr[2][2] + arr[1][1];
	//
	//dp[3][1] = arr[3][1] + dp[2][1];
	//dp[3][2] = max(arr[3][2] + dp[2][1], arr[3][2] + dp[2][2]);
	//dp[3][3] = arr[3][3] + dp[2][2];

	//dp[4][1] = arr[4][1] + dp[3][1];
	//dp[4][2] = max(arr[4][2] + dp[3][1], arr[4][2] + dp[3][2]);
	//dp[4][3] = max(arr[4][3] + dp[3][2], arr[4][3] + dp[3][3]);
	//dp[4][4] = arr[4][4] + dp[4][3];


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

	int result = 0;
	for (int i = 1; i <= n; i++) {
		result = max(result, dp[n][i]);
	}
	cout << result << endl;
}