1823 백준 수확 - C++, DP

1823번: 수확

#include <iostream>
#include <algorithm>
using namespace std;

int n, res;
int rice[2001];
int dp[2001][2001];


int DP(int left, int right, int count){
    if(left > right)
        return 0;
    
    if(dp[left][right])
        return dp[left][right];

    return dp[left][right] = max(DP(left+1, right, count+1) + rice[left] * count, DP(left, right-1, count+1) + rice[right] * count);
}

int main(){
    scanf("%d", &n);
    
    for(int i = 1; i <= n; i++)
        scanf("%d", &rice[i]);
    
    cout << DP(1, n, 1) << '\n';

}

---

처음 문제를 봤을때 덱을 이용하는건가 했는데 몇번째 수확하는지에 따라 가중치가 있기 때문에 단순 덱으로는 풀 수 없었고 DP 배열을 따로 뽑아서 풀이한 문제.

 int 안에 수들이 다 들어갔으며 dp 배열에는 [왼쪽 인덱스][오른쪽 인덱스]를 저장해서 풀이를 했다.

 

이 왜 골3?