[백준] 1823 수확 풀이

알고리즘

DP

풀이 과정

• n이 최대 2000이므로, 브루트 포스는 안될 것 같다. → 자연스레 DP를 하는 방향으로 갔다.
• DP는 작은 문제를 → 큰문제로 확장시켜 나가는 방식이다. 즉, 크기를 확장시키는 순서가 있어야 한다.
• ex) 13152 같은 경우, 양 끝쪽만 빠져나가는 것을 확인 할 수 있었다.

따라서 다음과 같은 점화식을 도출해냈다. 

BaseCode가 중요한데, start==end 일 경우, 맨 마지막 숫자이므로, dp[start][start] = arr[start] * n이 된다. 

이를 코드로 옮기면 다음과 같다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P1823 {
    public static BufferedReader br=  new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        int [] arr = new int [n];
        int [][] dp = new int [n][n];
        for (int i = 0 ; i< n ;  i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        // dp[start][end] = Math.max(dp[start+1][end] + cnt * a[start] ,  dp[start][end-1] + cnt * a[end]) ;
        // 크기 순으로 0 - n-1 까지
        for (int i = 0 ; i< n ; i++) {
            dp[i][i] = arr[i] * n;
        }
        for (int size = 1 ; size < n; size++){
            for (int start = 0 ; start < n ; start++) {
                int end = start + size;
                if (end >= n) continue;
                int cnt = n- (end-start);
                dp[start][end] = Math.max(dp[start+1][end] + cnt * arr[start], dp[start][end-1] + cnt * arr[end]);
            }
        }

        System.out.println(dp[0][n-1]);
    }

}