[JAVA]백준 1823번: 수확

www.acmicpc.net/problem/1823

1823번: 수확

 

1. 문제 설명

 

1*N 크기의 긴 밭에 심어진 벼를 수확하려고 한다. 벼는 양끝에 있는 벼만 수확을 할 수 있다.

 

수확을 하였을 때 얻을 수 있는 이익은 벼의 가치 v(i) * 벼를 수확한 순서 k의 합이다.

 

벼를 수확할 때 얻을 수 있는 최대 이익을 구하시오.

 

2. 풀이

 

dp로 Top down 방식과 Bottom Up 방식으로 풀 수 있다.

 

1) Top down (재귀)

 

cut(start, end, num) = 현재 남은 벼가 start 인덱스부터 end인덱스까지이고 num번째 수확할 순서일 때 최대 이익

= Math.max(cut(start+1,end,num+1)+num*v(start), cut(start, end-1, num+1)+num*v(end))

 

남은 벼가 start 인덱스부터 end 인덱스까지 있다면 start 위치의 벼를 수확하거나 end 위치의 벼를 수확하는 방법밖에 없다. 따라서 두 가지 경우의 수의 결과를 비교하고 최댓값을 가지면 된다.

 

2) Bottom Up (반복문)

 

dp [y][x] = 현재 남은 벼가 y인덱스부터 x인덱스까지이고 num번째 수확할 순서일 때 최대 이익

= Math.max(dp [y+1][x]+v(y)*num, dp [y][x-1]+v(x)*num)

 

현재 남은 벼가 y인덱스부터 x인덱스 까지라면 y인덱스의 벼를 수확하거나 x인덱스의 벼를 수확하는 경우의 수가 있다.

 

y인덱스의 벼를 수확하고 나서, 남은 벼가 y+1 인덱스부터 x인덱스까지이고 num+1번째 수확할 순서일 때 최대 이익은 dp [y+1][x]이다.

 

x인덱스의 벼를 수확하고 나서, 남은 벼가 y인덱스부터 x-1인 덱스까지이고 num+1번째 수확할 순서일 때 최대 이익은 dp [y][x-1]이다.

 

따라서 두 가지 경우에 각각 현재 수확할 벼의 가치를 더한다.

 

y인덱스의 벼를 수확하는 경우는 dp [y+1][x]+v(y)*num, x인덱스의 벼를 수확하는 경우는 dp [y+1][x]+v(x)*num이 되는 것이다.

 

최댓값을 구하고 dp [y][x]에 저장하면 된다.

 

num은 따로 변수로 지정하지 않고 전체 벼의 길이에 현재 남은 벼의 길이를 빼고 1을 더해 구할 수 있다.

 

3) 시간복잡도

 

두 가지 경우 모두 O(N^2)의 시간복잡도를 가진다.

 

3. 코드

 

1) Top down

import java.io.*;
import java.nio.Buffer;
import java.util.*;

public class Main {

    public static int[] rice_plant = new int[2001];
    public static int[][] dp = new int[2001][2001];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int rice_num = Integer.parseInt(br.readLine());

        for (int x = 1; x <= rice_num; x++) {
            rice_plant[x] = Integer.parseInt(br.readLine());
        }

        bw.write(String.valueOf(cut(1, rice_num, 1)));
        bw.flush();
        bw.close();
        br.close();

    }

    public static int cut(int start,int end,int num) {

        if(start>end)
            return 0;

        if(dp[start][end]!=0)
            return dp[start][end];

        int first = cut(start + 1, end, num + 1) + num * rice_plant[start];
        int last = cut(start, end - 1, num + 1) + num * rice_plant[end];

        dp[start][end] = Math.max(first, last);

        return dp[start][end];


    }




}

2) Bottom Up

 

import java.io.*;
import java.nio.Buffer;
import java.util.*;

public class Main {


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int rice_num = Integer.parseInt(br.readLine());
        int[][] dp = new int[rice_num + 1][rice_num + 1];
        int[] rice_plant = new int[rice_num + 1];

        for (int x = 1; x <= rice_num; x++) {
            rice_plant[x] = Integer.parseInt(br.readLine());

            dp[x][x] = rice_plant[x] * rice_num;

            for (int y = x - 1; y > 0; y--) {
                dp[y][x] = Math.max(dp[y + 1][x] + rice_plant[y] * (rice_num - x + y), dp[y][x - 1] + rice_plant[x] * (rice_num - x + y));
            }
        }



        bw.write(String.valueOf(dp[1][rice_num]));
        bw.flush();
        bw.close();
        br.close();

    }






}

1. Bottom up 2. Top down