[DP] 백준 2156. 포도주 시식

김성인·2024년 1월 11일
0

백준

목록 보기
1/10

DP 문제

https://github.com/SUNGIN99/JavaCodingTest/tree/main/%EB%B0%B1%EC%A4%80/Silver/2156.%E2%80%85%ED%8F%AC%EB%8F%84%EC%A3%BC%E2%80%85%EC%8B%9C%EC%8B%9D

  • 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
  • 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

연속으로 놓여있는 3잔의 경우 마실 수 없다를 점화식에 적용하는 것을 중점으로 고민하였다.


입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

1,000 * 10,000 = 10,000,000 -> int 형으로 해결 가능

n의 범위

1 ≤ n ≤ 10,000 이었기 때문에, n이 어떤 숫자이든 연속된 3잔이란 조건을 만족할 수 있는 방법이 필요하다고 생각함


case 1

n = 3 일때, [1, 2], [1, 3], [2, 3]을 선택하는 경우의 수가 필요하다.

6, 10, 13, 9, 8, 1 에서 3까지 최대로 마실 수 있는 경우의 수는 [2, 3]을 선택했을 때 !

여기서 DP[n-1], DP[n-2] + N[n]을 통해 [1, 2], [1, 3]에 대한 선택의 경우의 수는 고민할 수 있었지만, [2, 3]을 어떻게 구해야하나? 라는 고민이 있었음.


case 2

n = 4 일 때 DP[1], DP[2] 는 이미 쉽게 구할 수 있었다.

  • DP[1] = N[1]
  • DP[2] = DP[1] + N[2]

n = 4 일 때는 앞에 1을 선택했을 때와 안했을 때의 차이를 고민할 수 있었다.

  • 현재 포도주를 선택 O : [1, 2, 4], [1, 3, 4]
  • 현재 포도주를 선택 X : [1, 2], [1, 3], [2, 3]

점화식 도출

  • 여기서, DP[n-1]의 값이 연속된 2자리일 경우 현재 N[n]을 선택할 수 없다.

  • 만일 DP[n-1]이 DP[n-2] + N[n-1]일 경우(N[n-2]가 선택된), N[n]은 선택할 수 없다.
    그러므로, DP[n-2] + N[n]의 형태를 만들 수 있음.

  • 마지막으로, N[n-1]과 N[n]을 더하되, N[n-2]를 포함하지 않는 점화식 기준을 정할 수 있도록, N[n-1] + N[n] + DP[n-3]을 통해 N[n-2]가 포함되지 않은 값을 비교할 수 있다.

따라서,

  • DP[n-1] : 현재 포도주를 마신 양의 수의 합이, 앞의 연속된 포도주를 마셨을 때 보다 작은 경우
  • DP[n-2] + N[n]: 현재 포도주를 마시고, N[n-1] 포도주를 마시지 않았을 때의 경우
  • DP[n-3] + N[n-1] + N[n] : N[n-2] 포도주를 마시지 않고, 현재와 바로 앞 포도주를 마시는 경우

위 기준을 통해서 코드를 구현하여 정답을 도출할 수 있었다.

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
		
        // 1 ~ n 기준의 index를 맞추기 위해 n+1
        int[] grapeDrinks = new int[n+1];

        for(int i = 1; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            grapeDrinks[i]= Integer.parseInt(st.nextToken());

        }

        int[] dp = new int[n+1];
        dp[1] = grapeDrinks[1];
		
        // n == 1일 경우 N[1]만 도출하면 됨.
        if(n == 1){
            System.out.println(dp[1]);
            return;
        }

		// n >= 2 일 경우 N[1], N[0]을 통해서 비교 가능
        dp[2] = dp[1] + grapeDrinks[2];
        for(int i = 3; i<= n; i++){
            // a1: 현재 포도주를 선택하지 않고, 다음 포도주를 선택할 가능성을 둠.
            int a1 = dp[i-1]; 
            
            // a2: 현재 포도주를 선택하고, 바로 앞 포도주를 선택하지 않음.
            int a2 = dp[i-2] + grapeDrinks[i];
            
            // a3: 현재 포도주와 바로 앞 포도주를 선택하지않고, 앞앞 포도주를 선택하지 않음.
            int a3 = grapeDrinks[i] + grapeDrinks[i-1] + dp[i-3];

            dp[i] = Math.max(a1, a2);
            dp[i] = Math.max(dp[i], a3);
        }

        System.out.println(dp[n]);
        //System.out.println(Arrays.toString(grapeDrinks));
        //System.out.println(Arrays.toString(dp));
    }

}

결과

시간복잡도 : O(n)

profile
개발자가 꿈인 25살 대학생입니다.

0개의 댓글