[백준 2156번] 포도주 시식 - DP

백준 2156번 동적 계획법(Dynamic Programming)으로 풀 수 있는 문제이다.

 

문제를 읽어보면,

포도잔의 개수가 N개 있고, 이를 선택하여 마실 수 있다. 그러나 조건이 있다.
연속해서 위치한 3잔을 모두 마실 수는 없다. 여기서 가장 많은 양의 포도주를 마실 수 있는 양은 얼마인지 구해야한다.

 

점화식을 생각하게 되었고, 이전에 풀어봤던 문제 유형이랑 비슷해서 방법을 떠올리는 건 쉽게할 수 있었다.

그러나, 하나 사소한 부분에서 실수로 return문을 적지 않아 '왜 틀렸지...'하며 시간을 조금 낭비했다.

 

DP로 풀기 위해선 점화식을 세우는게 중요한데,

우선 초기 조건을 잘 확인해서 풀어야한다.

 

N이 1, 2, 3일 때를 나누어서 초기 조건을 세웠다.

if (N == 1) {
    System.out.println(grapeAmount[0]);
    return;
} else if (N == 2) {
    System.out.println(grapeAmount[0] + grapeAmount[1]);
    return;
} else if (N == 3) {
    int max = Math.max(grapeAmount[0] + grapeAmount[1], grapeAmount[0] + grapeAmount[2]);
    max = Math.max(max, grapeAmount[1] + grapeAmount[2]);
    System.out.println(max);
    return;
}

나는 여기서 마지막 N==3일 때의 조건에 return을 실수로 안해놓고 계속 왜 틀렸지 헤맸다...

 

여기서 N이 3일 때의 조건을 잘 보면 문제의 점화식에 감이 올 것이다.

3가지의 경우가 존재한다. (연속된 3개의 포도주를 선택할 수 없기에 다음과 같은 조건이 나온다.)

 

1️⃣ 현재 포도주(i)를 선택하고 전전(i-2)의 포도주를 선택하는 경우

dp[i-2] + grapeAmount[i]

2️⃣ 현재 포도주(i), 전 포토주(i-1) 그리고 전전전 포도주(i-3)을 선택하는 경우

grapeAmount[i-1] + dp[i-3] + grapeAmount[i]

3️⃣ 현재 포도주를 선택하지 않는 경우

dp[i-1]

 

이렇게 3가지 조건의 점화식이 나오게 되고, 현재의 가장 큰 값을 찾기 위해 3가지 조건을 비교하며 갱신하면 된다.

 

전체 소스코드는,

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

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[] grapeAmount = new int[N];

        for(int i = 0; i < N; i++) {
            grapeAmount[i] = Integer.parseInt(br.readLine());
        }

        if (N == 1) {
            System.out.println(grapeAmount[0]);
            return;
        } else if (N == 2) {
            System.out.println(grapeAmount[0] + grapeAmount[1]);
            return;
        } else if (N == 3) {
            int max = Math.max(grapeAmount[0] + grapeAmount[1], grapeAmount[0] + grapeAmount[2]);
            max = Math.max(max, grapeAmount[1] + grapeAmount[2]);
            System.out.println(max);
            return;
        }

        int[] dp = new int[N];
        dp[0] = grapeAmount[0];
        dp[1] = grapeAmount[0] + grapeAmount[1];
        int max = Math.max(grapeAmount[0] + grapeAmount[1], grapeAmount[0] + grapeAmount[2]);
        max = Math.max(max, grapeAmount[1] + grapeAmount[2]);
        dp[2] = max;

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

        System.out.println(dp[N-1]);
    }
}