[실버1, DP] 백준 2156 - 포도주 시식 (자바)

1. dp 문제를 읽고 항상 떠오르는 생각은, 이걸 DP로 어떻게 풀라는거지? 라는 생각이다... 아직 경험치가 많이 부족한가보다

2. 완전탐색을 하지 않고 dp 점화식을 어떻게 세울 수 있을지 아이디어가 전혀 떠오르지 않았다.

3. dp[i]의 정의는, i번째 와인잔까지 고려했을때 마실 수 있는 최대 와인 양 이다.

4.점화식은 dp[i]=max(dp[i−1],dp[i−2]+wine[i],dp[i−3]+wine[i−1]+wine[i]) 다.

5. i번째 와인잔까지 고려했을때 마실 수 있는 최대 와인 양을 구하기 위해서는, 즉, dp[i]를 구하기 위해서는, 세가지 경우를 고려해야한다.

6. (1) 현재 i번째의 와인잔을 마시지 않는 경우 (i-1번째까지의 마실 수 있는 최대 와인 양)

    (2) i-2번째까지의 마실 수 있는 최대 와인 양 + i번째 와인을 마시는 경우

    (3) i-3번째까지의 마실 수 있는 최대 와인 양 + i-1번째 와인을 마시는 경우 + i-1번째 와인을 마시는 경우

7. 이 세가지 경우만 고려한다면, 항상 최적의 최대 와인 양만 구할 수 있다.

 

제출코드

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

public class testtest {
    static int N, wine[];
    static Integer dp[];

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        init();
        process();
    }


    private static void process() {

        dp[0] = 0;
        dp[1] = wine[1];

        if(N>=2){
            dp[2] = wine[1] + wine[2];
        }

        for (int i = 3; i <= N; i++) {
            dp[i] = Math.max(Math.max(dp[i-1], dp[i-2]+ wine[i]), dp[i-3] + wine[i-1] + wine[i]);
        }

        System.out.println(dp[N]);

    }


    private static void init() throws IOException {

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

        // dp[n] = n번째까지 먹을 수 있는 최대 와인의 양
        // dp는 하위 문제들의 결과를 어떻게 결합하여 상위 문제의 결과를 만들 수 있을지 생각
        // n == 3 : 1,5,3
        // n == 4 : 1,5,3,7
        // n == 5 : 1,5,3,7,2
        dp = new Integer[N + 1];
        wine = new int[N + 1];

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