[백준 Gold 3] 1823 수확 - Java

문제 링크 : www.acmicpc.net/problem/1823

1823번: 수확

 

접근 과정

• 벼가 일렬로 존재한다고 가정하고, 왼쪽 끝과 오른쪽 끝의 벼 중 하나를 수확!
• DFS 방법으로 왼쪽 끝의 벼와 오른쪽 끝의 벼를 수확하는 경우를 모두 탐색 => 시간초과
• DP 방법으로 DP[][] : i번째 벼부터 j번째 벼가 남아있는 상태에서의 최대 수확량이라고 정의

 

 

소스 코드 및 결과

   Code 1 : DFS

import java.io.*;

/* 
    수확 
    시간초과
*/

public class BOJ1823 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        arr = new int[n + 1]; // 벼

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

        max = 0;
        cost = new int[n + 1];

        dfs(1, 1, n);

        System.out.println(max);
    }

    static int[] arr;   
    static int[] cost; // 수확 시기때마다 수확한 벼의 가치
    static int max;

    static void dfs(int index, int left, int right){
        if (left == right) { // 벼가 1개 남은 경우
            int t = 0;
            for(int i = 1; i<cost.length-1; i++){
                t +=(i*cost[i]);
            }
            t += (index*arr[left]);
            max = Math.max(max, t);
            return; 
        }       

        // 왼쪽 끝의 벼를 수확하는 경우
        cost[index] = arr[left];
        dfs(index+1, left+1, right);

        // 오른쪽 끝의 벼를 수확하는 경우
        cost[index] = arr[right];
        dfs(index+1, left, right-1);
    }
}

   결과 

 

   Code 2 : DP

import java.io.*;

/* 
    수확 
*/

public class BOJ1823 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        arr = new int[n + 1];

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

        dp = new int[n+1][n+1];

        System.out.println(findDP(1, n));
       
    }

    static int n;
    static int[] arr;   
    static int[][] dp; // i에서 j범위의 벼가 남았을 때의 최대 가치

    static int findDP(int start, int end){
        
        if (start > end) { // 모두 수확한 경우
            return 0;
        }

        if (dp[start][end] != 0) { // 이미 계산된 최대 가치가 존재하는 경우
            return dp[start][end];
        }

        int index = n-(end-start); // 현재 수확 순서

        // Start~End 벼가 있을 때의 최대가치 
        //      = Max(왼쪽 벼를 수확했을 때 X 왼쪽 벼의 수확가치, 오른쪽 벼를 수확했을 때 X 오른쪽 벼의 수확가치)   
        dp[start][end] = Math.max(findDP(start+1, end)+(arr[start]*index), findDP(start, end-1)+(arr[end]*index));

        return dp[start][end];
    }
}

 

   결과 :