[Java] 백준 포도주 시식

1. 문제분석

포도주를 어떻게 하면 많이 마실 수 있는지 확인하는 문제다.

연속해서 3잔은 마실 수 없고 그 중에서 가장 많이 마시는 경우를 해결해야 한다.

이 문제의 경우 백준의 계단 오르기(?)문제와 동일하다 3계단을 연속해서 올라갈 수 없고 마지막을 무조건 밟아야 하는 경우지만 이 문제는 마지막을 마시지 않아도 된다.

 

먼저 점화식을 세워보기 위해 테스트 케이스 1인 6 10 13 9 8 1를 보자.

첫번째 6을 마신 경우는 최대가 6이된다. -> DP[1]

두번째까지는 연속해서 마셔도 된다 최대가 6+6 = 12가 된다. -> DP[2]

세번째부턴 조건에 부합하게 마셔야 한다. 여기서 2가지를 볼 수 가 있다.

 

-세번째 포도주를 먹는 경우

1. 첫번째까지의 최댓값 + 세번째의 값 -> DP[1] + arr[3]이 된다. 

2. 0번째까지의 최댓값 + 1번째의 값 + 3번째의 값 -> DP[0] + arr[1] + arr[3]이 된다.

-세번째 포도주를 안먹는 경우

1. 전단계 까지의 최대값 -> DP[2]

 

총 3가지의 경우 중 최대값을 구하면 된다.

2. 구현

import java.io.*;
import java.nio.Buffer;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int totalTestCase = Integer.parseInt(br.readLine());
        int[] arr = new int[totalTestCase + 1];
        int[] dp = new int[totalTestCase + 1];

        for(int i =1; i<totalTestCase+1; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        dp[1] = arr[1];
        if(totalTestCase > 1){
            dp[2] = arr[1] + arr[2];
        }
        //무조건 2부터 구하는게 아니다. 조건을 보고 3개가 될 수도있고 4개가 될 수도 있는거다.
        for(int i = 3; i<totalTestCase+1; i++){
            /**
             * 내가 현재 포도주를 먹을까 말까?
             * 현재자리 + 전전자리의 최댓값(3개 연속은 안되니까)
             * 현재자리 + 전전전자리의 최댓값 + 전자리의 값(3개 연속은 안되니까)
             * 전자리의 최댓값(난 안먹을꺼다?)
             * */
            dp[i] = Math.max((dp[i-2]+arr[i]),Math.max(dp[i-1],(dp[i-3]+arr[i-1]+arr[i])));
        }
        System.out.println(dp[totalTestCase]);
    }
}

여기서 볼점은 dp[2]의 값이다. 

어찌 됐건 dp[2]는 배열의 크기가 1보다 크다면 arr[0]+arr[1]이 된다.

초기화를 해주고 3번째 경우부터 보면 된다.

3. 마무리

나는 항상 dp를 2부터 구해야한다고 생각을 했는데 어찌됐건 값만 구하면 되는 것이였다.

또한 3개중 최댓값을 처음에는 생각했지만 왜 3개가 나오지? 2개가 나와야하는데.. 라는 생각으로 한참을 해맸다.