[알고리즘] 백준 2156 포도주 시식

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

2156번: 포도주 시식

 

import java.util.Scanner;

public class BJ_2156 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] juice = new int[n + 1];
        int[] dp = new int[n + 1];

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

        dp[1] = juice[1];

        if (n >= 2) {
            dp[2] = juice[1] + juice[2];
        }

        if (n >= 3) {
            dp[3] = Math.max(dp[1] + juice[3], Math.max(dp[2], juice[2] + juice[3]));
        }

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

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

DP 문제다.

 

포도주를 연속해서 3번 집지 못하기 때문에 경우의 수와 점화식은 다음과 같다.

 

■OOX : dp[i - 1]

■OXO : dp[i - 2] + juice[i]

■XOO : dp[i - 3] + juice[i - 1] + juice[i]

 

(■)는 이전값을 나타낸다.

 

즉 ■에는 다수의 포도주가 있을 수 있는데 이는 DP를 통해 구하였기 때문에 문제 조건을 위배하지 않으면서 포도주를 최대로 고른것들이다.

 

점화식에서 i - 3 인덱스가 쓰이고 있기 때문에 dp[1] ~ dp[3] 까지는 하드코딩으로 박아준 다음 문제를 풀어야 한다.

 

dp[i]의 값은 위 점화식 중에서 최대값을 뽑아내면 된다.