(C++) - 백준(BOJ) 1823번 : 수확, 13002번 : Happy Cow

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

1823번: 수확

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

13002번: Happy Cow

dp 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

 1. n, 벼의 가치를 입력받을 일차원 배열 a, 점화식을 계산할 이차원 배열 d를 선언합니다.  2. 아직 한 번도 계산하지 않았음을 나타내기 위해 d배열을 -1로 초기화합니다. 3. n입력 후 n만큼 a에 벼 가치 정보를 입력합니다.

 

📔 풀이과정

점화식을 세웁니다. d[l][r]은 왼쪽에서 l-1번째까지의 벼를 수확하고 오른쪽에서 r + 1까지의 벼를 수확했을 때 얻는 최대 이익입니다. 이렇게 생각했을 경우 점화식은 다음과 같습니다.

 d[l][r] = max(l을 선택한 경우, r을 선택한 경우 얻을 수 있는 이익).

메모이제이션을 사용하므로 d[l][r]에 대해서는 최대 한 번의 계산만을 수행합니다. n = 2000이 최대이므로 시간복잡도는 O(2000^2)가 됩니다.

 

기저 케이스는 l > r이 될 경우 유효하지 않으므로 0을 반환해줍니다.

 

 dp함수를 수행한 결과를 반환합니다.

 

📔 정답출력

dp함수의 결과 값을 출력합니다.

---

📕 Code

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

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

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);
}