문제 링크
문제
티어: 골드 3
알고리즘: dp
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) 가 주어진다.
출력
첫째 줄에 얻을 수 있는 최대 이익을 출력한다.
풀이
최대 이익으로 수확을 진행해야 한다.
매번 선택으로 인한 경우의 수가 x2로 증가하기 때문에 완탐은 불가능하다.
또한 매번 선택하는 과정에서 최선의 선택이 있을 것 같지만, 그렇지 않다.
예를 들어 4 1 1 1 4 4 4 5라고 했을 때 4와 5를 선택할 때는 4가 아닌 5를 선택하는게 최적일 것이다.
그리디도 아니고 완탐도 아니기 때문에 dp로 풀어야 한다.
다음과 같은 예제가 있다.
1 3 1 5 2
여기서 3 1 5만 남았다고 생각해 보자, 이 때 경우의 수는 1 -> 2, 2 -> 1이 있다.
이러한 경우를 매번 구한다면 시간 초과가 발생할 것이다. 그래서 메모제이션을 활용해야 한다.
그래서 1 -> 2, 2 -> 1중 최댓값을 활용하고, 수확을 진행한다.
3 1 5라는건 어떻게 표현할 수 있을까? k가 2번 진행했음을 알 수 있다.
그리고 k가 1번 진행한 값을 활용한다. 이러한 아이디어로 점화식을 유도할 수 있다.
k가 1일 때 모든 경우의 수는
왼쪽 하나, 오른쪽 하나다. 이는 dp[0][1], dp[1][0]으로 표현할 수 있다.
그래서 dp[A][B]는 왼쪽에서부터 A까지, 오른쪽에서부터 B까지의 최댓값으로 정의할 수 있다.
k가 2일 때는 dp[0][2], dp[1][1], dp[2][0]이다.
dp[1][1]를 구할 때 k가 1일 때 값을 사용한다.
그래서 dp[1][1] = Math.max(dp[0][1] + 1 k, dp[1][0] + dp[1][0] + 2 k) 최댓값을 구할 수 있다.
k는 N번까지 반복하고, 한 번에 반복에서 0 ~ k번 반복하기 때문에 이 풀이의 시간 복잡도는 O(N^2)된다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
int[][] dp = new int[N + 1][N + 1]; // [A][B] 왼쪽부터 A까지, 오른쪽부터 B까지의 최댓값
int answer = 0;
for (int k = 1; k <= N; k++) { // k번
for (int i = 0; i <= k; i++) { // 왼쪽은 i번, 오른쪽은 k - i번
int r = k - i;
if (i - 1 >= 0) { // 왼쪽에서 arr 요소를 추가하는 경우
dp[i][r] = dp[i - 1][r] + arr[i - 1] * k;
}
if (r - 1 >= 0) { // 오른쪽에서 arr 요소를 추가하는 경우
dp[i][r] = Math.max(dp[i][r], dp[i][r - 1] + arr[N - r] * k);
}
answer = Math.max(answer, dp[i][r]);
}
}
System.out.println(answer);
}
}