백준 C++ | #24 BOJ1823 수확 C++ 문제 풀이

1823번: 수확 (acmicpc.net)

1823번: 수확

 

다이나믹 프로그래밍.. 너무 어렵당

그래도 왜 전역변수로 DP용 배열을 만드는지 알게 되었다. 

DP용 배열이 전역변수로 있으면, 재귀함수로 구현했다고 하더라도, 같은 값을 여러 번 구하지 않아도 된다. 

 

#include <bits/stdc++.h>
using namespace std;
int n, a[2001], d[2001][2001];

int dp(int l, int r, int k) {
	if (l > r) {
		return 0;
	}
	int& ret = d[l][r];
	if (ret != -1) {
		return ret;
	}
	return ret = max(dp(l, r - 1, k + 1)+a[r]*k, dp(l+1, r, k+1)+a[l]*k);
}

int main() {
	memset(d, -1, sizeof(d));

	cin >> n;
	
	for (int i = 0; i < n; i++) cin >> a[i];


	cout << dp(0,n-1,1);
	return 0;
}