백준 2156 : 포도주 시식 [JAVA]

[문제 링크]

https://www.acmicpc.net/problem/2156

[난이도]

- Silver 1

 

[알고리즘]

- DP

 

[코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        if (n == 1) {
            System.out.println(wine[1]);
            return;
        }

        // 초기값 설정
        int[] dp = new int[n+1];
        dp[1] = wine[1];
        if (n > 1) {
            dp[2] = wine[1] + wine[2];
        }

        // 점화식 도출
        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(dp[i-1], Math.max(dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i]));
        }
        /**
         * dp[i-1]  = i번째 잔을 안마시는경우
         * dp[i-2] + wine[i] = i-1번째잔을 마시지 않고 현재와인을 마시는 경우
         * dp[i-3] + wine[i-1] + wine[i] = i번째 잔과 i-1번째 잔을 마시고, i-2번째 잔을 마시지 않는 경우
         */

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

[풀이]

1. DP 배열 정의: dp[i]는 i번째 포도주 잔까지 최대로 마실 수 있는 포도주의 양을 의미합니다.
2. 점화식 수립:
   • dp[i]는 세 가지 경우 중 최댓값이 됩니다:
     1. i번째 잔을 마시지 않는 경우: dp[i-1]
     2. i번째 잔을 마시고, i-1번째 잔을 마시지 않는 경우: dp[i-2] + wine[i]
     3. i번째 잔과 i-1번째 잔을 마시고, i-2번째 잔을 마시지 않는 경우: dp[i-3] + wine[i-1] + wine[i]
3. 초기 조건 설정:
   • dp[0]은 첫 번째 잔을 마시는 경우입니다.
   • dp[1]은 첫 번째와 두 번째 잔을 마시는 경우입니다.
   • dp[2]은 세 번째 잔까지의 최댓값을 고려합니다.