백준 1823 - 수확 (C++)

문제

• 문제 링크

  
   BOJ 1823 - 수확 
  

• 문제 요약

$N$개의 벼와 그 가치가 주어진다.
문제에 정의된 규칙대로 벼를 수확할 때 얻을 수 있는 최대 이익을 구해보자.

• 제한

TL : $1$ sec, ML : $128$ MB




$1 ≤ N ≤ 2,000$

$1 ≤ N_i ≤ 1,000$

알고리즘 분류

• 다이나믹 프로그래밍(dp)

풀이

   결국 양 끝 점에서만 상태가 변화 한다는 것에 주목하면 이미 문제를 푼 것이나 다름 없다.
다음과 같이 점화식을 정의하자.

$dp[p][q]$ : 현재 구간 $[p, q]$를 보고 있을 때 얻을 수 있는 최대 이익.

만약 왼 쪽 점을 취한다면 $a[p] * (n - (q - p))$ 의 이득이 발생하고, 오른 쪽 점을 취한다면 $a[q] * (n - (q - p))$ 의 이득이 발생한다.

기저 사례는 당연히 $p$ == $q$ 일 때가 되겠다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int n, a[2001], dp[2001][2001];
 
int f(int p, int q)
{
    if (p == q) return a[p] * n;
    int& t(dp[p][q]);
    if (!~t)
        t = 0, t = max({ t, f(p + 1, q) + a[p] * (n - (q - p)), f(p, q - 1) + a[q] * (n - (q - p)) });
    return t;
}
int main()
{
    memset(dp, -1, sizeof dp);
    cin >> n;
    for (int i(1); i <= n; cin >> a[i++]);
    cout << f(1, n);
}

comment

끝