[Gold 3] 1823 수확

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

1823번: 수확

 

이 문제는 DP를 이용하여 해결할 수 있다.

벼의 최대 개수는 2000개이다. 

또한 벼를 수확할 수 있는 방법은 2000 * 2000개의 방법이 있다.

따라서 DP 배열을 2000 x 2000의 크기를 할당해야한다.

 

벼의 가치를 입력받았다면, 0번째 인덱스 부터 N - 1번째 인덱스까지의 합 중에 최대 값을 알아봐야한다.

이는 아래 점화식을 사용하면 해결할 수 있다.

DP[start][end] = MAX(start를 선택한 경우, end를 선택한 경우 얻을 수 있는 이익)

 

start를 선택한 경우는 rice[start] * counter로 표현할 수 있다.

마찬가지로 end를 선택한 경우는 rice[end] * counter로 표현할 수 있다.

 

이어서 start를 선택한 경우와 end를 선택한 경우 가치를 알아볼 다음 벼를 골라야한다.

이는 start를 선택된 경우 start 포인터를 한칸 옮기기만 하면 된다.

end를 선택한 경우에도 end 포인터를 한칸 옮기기만 하면된다.

위 경우가 성립하는 이유는 "첫 번째 벼를 수확을 하였다면 두 번째 벼와 N번째 벼를 수확을 할 수 있다." 라는 조건 때문이다.

만약 start가 2번째 벼인 경우 3번째 벼와 N 번째 벼를 수확할 수 있기 때문에 start + 1과 end를 넘겨 위 조건에 만족하도록 한다.

 

예제를 통해 위 점화식을 풀어본다면 DP 배열은 아래와 같다.

 

벼 배열

1

3

1

5

2

 

연산 결과

5	19	22	40	43 (정답)
0	15	19	38	42
0	0	5	29	36
0	0	0	25	33
0	0	0	0	10

 

연산 과정

MAX( 0 + rice[0] x 5, 0 + rice[0] x 5)	MAX(DP[1][1] + rice[0] x 4, DP[0][0] + rice[1] x 4)	MAX(DP[2][2] + rice[0] x 3, DP[0][1] + rice[2] x 3)	MAX(DP[1][3] + rice[0] x 2, DP[0][2] + rice[3] x 2)	MAX(DP[1][4] + rice[0] x 1, DP[0][3] + rice[4] x 1)
0	MAX( 0 + rice[1] x 5, 0 + rice[1] x 5)	MAX(DP[2][2] + rice[1] x 4, DP[1][1] + rice[2] x4)	MAX(DP[2][3] + rice[1] x 3, DP[1][2] + rice[3] x 3)	MAX(DP[2][4] + rice[1] x 2, DP[1][3] + rice[4] x 2)
0	0	MAX( 0 + rice[2] x 5, 0 + rice[2] x 5)	MAX(DP[3][3] + rice[2] x 4, DP[2][2] + rice[3] x 4)	MAX(DP[3][4] + rice[2] x 3,  DP[2][3] + rice[4] x 3)
0	0	0	MAX( 0 + rice[3] x 5, 0 + rice[3] x 5)	MAX(DP[4][4] + rice[3] x 4, DP[3][4]+rice[4]x4)
0	0	0	0	MAX( 0 + rice[4] x 5, 0 + rice[4] x 5)

 

메모리제이션을 사용하기 위해 제귀 함수를 사용하고, 만약 DP[start][end] 에 해당하는 가치를 이미 계산 했다면 기존에 구했던 값을 반환하도록 한다.

마지막으로 start 포인터가 end 포인터를 넘어가게 된다면 0을 반환하여 잘못된 연산을 하지 못하도록한다.

이는 이진 탐색을 사용하는 것이며, 이를 통해 O(2000^2)의 시간 복잡도를 가지게 된다.

 

 

#include<iostream>
#include<algorithm>
using namespace std;
 
int N;
int rice[2001];
int dp[2001][2001];

int solve(int start, int end, int counter){
    if(start > end) return 0;

    if(dp[start][end])
        return dp[start][end];
    
    return dp[start][end] = max(solve(start+1, end, counter + 1)+ rice[start] * counter,
        solve(start, end-1,counter + 1) + rice[end] * counter);
}
 
int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

    cin>>N;
    for(int i = 0;i<N;i++)
        cin>>rice[i];

    cout<<solve(0, N - 1, 1)<<'\n';
}