[Gold III] 수확 - 1823 (Java)

문제 링크

분류

다이나믹 프로그래밍

 

문제 설명

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 테이블)

시간 복잡도 O(n) 공간 복잡도 O(n)

아이디어: dp[n] 을 n번째 벼까지 수확 했을 때의 최대 값을 저장하는 공간으로 저장한다, dp[0] = 0 이다.

맨 처음과 맨 마지막 중에서 더 작은 값을 선택해서 수확한다. 만약 두 개의 값이 동일 하다면 작은 값이 더 가까운 쪽으로 수확한다.

모든 경우를 체크하지 못 하여 더 세밀한 DP 테이블 관리가 필요했다.

import java.io.*;
import java.util.*;

public class Main {
    public static int sti(StringTokenizer st){
        return Integer.parseInt(st.nextToken());
    }
    public static long stl(StringTokenizer st){
        return Long.parseLong(st.nextToken());
    }
    static boolean judge(int[] array,int start, int end){
        while(start<=end&&array[start]==array[end]){
            if(array[start]>array[end])
                return true;
            else if(array[end]>start)
                return false;
            start++; end--;
        }
        return true;
    }

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] dp = new long[n+1];
        int[] array = new int[n+1];
        // 가치: array[i]*i

        for (int i = 1; i <= n; i++) {
            array[i] = Integer.parseInt(br.readLine());
        }
        boolean way = true;

        int count = 1;
        int start = 1; int end = n;
        while(start<=end){
            if(array[start]==array[end]){
                way = judge(array,start+1,end-1);
                if(way)
                    dp[count] = Math.max(dp[count],dp[count-1]+ (long) array[end--] *count);
                else
                    dp[count] = Math.max(dp[count],dp[count-1]+ (long) array[start++] *count);
            }
           else if(array[start]>array[end])
               dp[count] = Math.max(dp[count],dp[count-1]+ (long) array[end--] *count);
           else
               dp[count] = Math.max(dp[count],dp[count-1]+ (long) array[start++] *count);
           count++;
        }
        System.out.println(dp[n]);
    }
}

성공한 풀이 (동적 프로그래밍)

시간 복잡도 O(n^2) 공간 복잡도 O(n^2)

<아이디어>

1 단계: DP 테이블 설정

• dp[i][j]는 제일 왼쪽 끝에서 i번 칸 만큼 수확하고 제일 오른쪽 끝에서 j번 칸 만큼 수확하여 얻은 작물의 최대 가치
• i+j <= n 인 경우에만 성립 그 외의 공간은 관리 x (아래는 사진 예시)

2 단계: 초기 테이블 세팅

3 단계: DP 테이블을 갱신하는 규칙을 찾아 로직을 구현

제일 위에 예시와 마찬가지로 벼에 대한 가치의 배열이 (인덱스 1~n) {1, 2, 3, 4, 5) 일 때

왼쪽으로 2번, 오른쪽으로 1번 수확한 상황에서 추가로 4번째 작물을 수확해야 하는 경우 갱신 방법

• 왼쪽의 벼를 추가로 수확 하는 경우
  • dp[3][1] = dp[2][1]+(3 + 1) *array[3];
• 오른쪽의 벼를 추가로 수확 하는 경우
  • dp[2][2] = dp[2][1]+(2+2)*array[n-2+1];

4 단계: 목표하고자 하는 내용을 출력

모든 벼를 수확했을 때 최대값을 출력해야 하므로 i+j == n 인 경우의 값 중 최고값을 출력

import java.io.*;
import java.util.*;

public class Main {
    public static int sti(StringTokenizer st){
        return Integer.parseInt(st.nextToken());
    }
    public static long stl(StringTokenizer st){
        return Long.parseLong(st.nextToken());
    }

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[][] dp = new long[n+1][n+1];
        int[] array = new int[n+1];
        dp[0][0] = 0;
        // 가치: array[i]*i
        for (int i = 1; i <= n; i++) {
            array[i] = Integer.parseInt(br.readLine());
        }
		// 초기 테이블 세팅
        for (int i = 1; i <= n; i++) {
            dp[i][0] = dp[i - 1][0] + (long) array[i] * i;
            dp[0][i] = dp[0][i-1] + (long)array[n-i+1]*i;
        }
		// 로직
        long ans = 0;
        for (int i = 1; i <=n; i++) {
            for (int j = 1; j <=n; j++) {
                if(i+j>n) continue;
                dp[i][j] =Math.max(dp[i][j],dp[i-1][j]+ (long) (i + j) *array[i]);
                dp[i][j] =Math.max(dp[i][j],dp[i][j-1]+(long) (i+j)*array[n-j+1]);

                if(i+j==n)
                    ans = Math.max(ans,dp[i][j]);
            }
        }
        // 출력
        if(n==1)
            System.out.println(array[n]);
        else System.out.println(ans);
    }
}