[BOJ] 1823 - 수확

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

BOJ - 수확

문제 유형: 다이나믹 프로그래밍

문제 난이도: Gold III

시간 제한: 1초

메모리 제한: 128MB

 

문제

1 × N 크기의 긴 밭에 벼가 심어져 있다. 준희는 이 벼를 수확 하려고 한다. 그런데 가운데 있는 벼를 수확을 하려면 끝에서 가운데까지 헤집고 들어가야 하므로 양 끝에 있는 벼만 수확을 할 수 있다. 처음에는 첫 번째와 N번째 벼를 수확을 할 수 있을 것이며 만약에 첫 번째 벼를 수확을 하였다면 두 번째 벼와 N번째 벼를 수확을 할 수 있다.

수확을 하였을 때 얻을 수 있는 이익은 다음과 같다. 만약에 그 벼의 가치가 v(i)라고 하고 그 벼를 k번째로 수확을 한다고 하면 v(i) × k 만큼의 이익을 얻게 된다.

만약에 벼의 가치가 차례로 1 3 1 5 2 라고 하고 첫 번째, 다섯 번째, 두 번째, 세 번째, 네 번째의 순서대로 수확을 한다고 하면 1×1 + 2×2 + 3×3 + 4×1 + 5×5 = 43 이 되어 43 만큼의 이익을 얻게 된다. 그리고 이 값이 저 벼로 얻을 수 있는 최대 이익이 된다.

우리가 구해야 할 값은 다음과 같다. 벼의 개수 N과 벼의 가치가 주어져 있을 때, 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다.

 

출력

첫째 줄에 얻을 수 있는 최대 이익을 출력한다.

 

풀이

dp[l][r] = [l, r]범위의 최대 얻을 수 있는 이익으로 한다.

이러면, 탑-다운 재귀로 쉽게 풀 수 있다.

왼쪽을 베는 경우와 오른쪽을 베는 경우 중 최고의 값을 가져오면 되기 때문이다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll solve(int seqno, int l, int r, vector<int> &v, vector<vector<ll>> &dp) {
    if (l > r) return 0;
    if (dp[l][r] != -1) return dp[l][r];

    ll left = solve(seqno + 1, l + 1, r, v, dp) + v[l] * seqno;
    ll right = solve(seqno + 1, l, r - 1, v, dp) + v[r] * seqno;

    return dp[l][r] = max(left, right);
}

int main(int argc, char *argv[]) {
    int n;
    cin >> n;
    vector<int> v(n);
    for (auto &i : v) cin >> i;

    vector<vector<ll>> dp(n, vector<ll>(n, -1));

    cout << solve(1, 0, n - 1, v, dp) << "\n";

    return 0;
}