[백준] 2156 - 포도주 시식 | Java

📌 문제 정보

[2156: 포도주 시식]

💡 접근 방식

연속으로 3개를 마실 수 없다.
이때 i번째 포도주를 마시는 경우의 수는 3가지 이다.

1. i-1번 안 마시고, i번 마시기 -> dp[i-2] + wine[i]
2. i-2번 안 마시고, i-1번, i번 마시기 -> dp[i-3] + wine[i-1] + wine[i]
3. i번 안 마시기 -> wine[i]

이 세 경우에서 최대를 찾아 dp[i]에 저장하면 된다.

✅ 코드

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

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];
        int[] dp = new int[n+1];

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

        dp[1] = wine[1];
        if (n >= 2) dp[2] = wine[1] + wine[2];

        if (n < 3) {
            System.out.println(dp[n]);
            return;
        }

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

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

    }

}

🧠 배운 점 & 회고

처음에 i-2번 안 마시고, i-1번, i번 마시는 경우를
dp[i-1] + wine[i]로 세웠었다..
이렇게 되면 i-2과 i-1을 마시고, i까지 마시는 경우가 포함될 수 있는 문제가 있었다!

🧾 결과