99클럽 코테 스터디 12일차 TIL + 포도주 시식

 

- 오늘의 학습 키워드

포도주 시식

- 풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] wine = new int[n + 1]; // 1-based index

        for (int i = 1; i <= n; i++) {
            wine[i] = sc.nextInt();
        }

        System.out.println(solution(n, wine));
    }

    private static int solution(int n, int[] wine) {
        int[] dp = new int[n + 1];

        if (n >= 1) dp[1] = wine[1];
        if (n >= 2) 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]));
        }

        return dp[n];
    }
}

 

- 오늘의 회고

dp[i]는 i번째 포도주까지 고려했을 때, 최대로 마실 수 있는 포도주의 양

선택할 수 있는 경우는 세 가지다.

1. i번째 잔을 안 마시는 경우 → dp[i-1]
2. i-1번째는 안 마시고 i번째와 i-2번째를 마시는 경우 → dp[i-2] + wine[i]
3. i-2번째는 안 마시고 i-1번째, i번째를 마시는 경우 → dp[i-3] + wine[i-1] + wine[i]