백준 1823번 수확 (C++)

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

1823번: 수확

 

비슷한 문제를 몇 개 풀어본적이 있어서 비교적 쉽게 풀 수 있었다.

 

최댓값을 보고 생각해야하는 것은 bfs이다. 그러나 N의 개수를 보고 빠르게 접는다.

양방향을 보고 생각해야하는 것은 투포인터, 이분탐색, dp이다. 그리고 모든 방법을 고려해야하기 때문에 이분탐색과 투포인터는 제외시켜야한다. 그래서 남는 선택지는 dp이다.

 

두가지 선택지가 존재한다. 앞을 먼저 수확하거나 뒤를 먼저 수확하거나. 이것을 코드로 바꿔보면

 

dp[left] -> 왼쪽 끝을 수확

dp[right] -> 오른쪽 끝을 수확

 

그러나 1차원 배열로는 투포인터나 마찬가지다. 그래서 dp[left][right]를 만들어서 left~ right일 때 최대 수확량을 계산해 메모이제이션하여 사용하도록 한다.

 

dp[left][right] = left에서 right를 수확했을 때 최대값

 

left는 0으로 고정시키고 right를 늘려보자

 

예제처럼 1 3 1 5 2 라면

 

dp[0][0] = 1

dp[0][1] = 왼쪽 먼저 선택 or 오른쪽 먼저 선택

 

두번째 디피에서 점화식을 도출할 수 있다.

-> max(dp[0][0] + 왼쪽 선택, dp[1][1] + 오른쪽 선택)

즉, 

 

dp[left][right] = max(dp[left + 1][right] + 왼쪽 값, dp[left][right - 1] + 오른쪽 값)

 

이것을 계속 반복해야한다 언제까지? left와 right가 같아질 때 까지 left와 right가 같다는 것은 수확을 모두 했다는 의미 이므로 마지막 cnt * 마지막 값 으로 리턴해준다.

 

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <vector>
#define ll long long

using namespace std;

vector<int> arr;
int N;
ll dp[2001][2001];
int recussion(int left, int right, int cnt){
    if(left == right) return dp[left][right] = cnt * arr[left];
    else if(dp[left][right] != -1) return dp[left][right];
    
    return dp[left][right] = max(recussion(left + 1, right, cnt + 1) + arr[left] * cnt, 
                                    recussion(left, right - 1, cnt + 1) + arr[right] * cnt);
    
}

int main()
{
    cin >> N;
    
    for(int i = 0; i < 2001; i++)
        for(int j = 0 ; j < 2001; j++)
            dp[i][j] = -1;
    
    arr = vector<int>(N);
    for(int i = 0; i < N; i++){
        cin >> arr[i];
    }
    ll answer = 0;
    answer = recussion(0, N - 1, 1);
    
    cout << answer << '\n';
}