백준 2156번) 포도주 시식 java

 

분석

---

 

 

일단 포도주를 3개라고 가정해보자

 

포도주를 제일 많이 마시는 경우의 수는

1. 첫 번째 , 두 번째 포도주를 마시는 경우

2. 세 번째 , 첫 번째 포도주를 마시는 경우

3. 세 번째 , 두 번째 포도주를 마시는 경우

 

크게 3가지가 나올 수 있다.

 

이렇게 생각하면 다음과 같은 점화식을 세울 수 있다.

dp[num] = max(max(dp[num - 3] + value[num - 1] + value[num], dp[num - 2] + value[num]),dp[num-1]);

 

3가지 경우의 수를 비교해주면 된다 !

 

 

코드

---

import java.util.Arrays;
import java.util.Scanner;

import static java.lang.Math.max;


public class Main {

    static long[] dp;
    static long[] value;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int num = sc.nextInt();
        value = new long[10001];
        dp = new long[10001];
        for (int i = 1; i <= num; i++) {
            value[i] = sc.nextInt();
        }
        dp[0] = 0;
        dp[1] = value[1];
        dp[2] = value[2] + value[1];
        if (num == 2) {
            System.out.println(dp[2]);
            return;
        }
        for (int i = 3; i <= num; i++) {
            dp(i);
        }
        System.out.println(dp[num]);


    }

    static void dp(int num) {
        dp[num] = max(max(dp[num - 3] + value[num - 1] + value[num], dp[num - 2] + value[num]),dp[num-1]);
    }

}