[Java] 백준 2156번: 포도주 시식

[문제 바로 가기] - 포도주 시식

유형 : 다이나믹 프로그래밍

💡 아이디어

이전에 풀이했던 계단 오르기 문제와 비슷하다고 생각하여 처음엔 해당 풀이로 먼저 풀이해보았다.

        int[][] dp = new int[n + 1][3];
        dp[1][1] = wine[1];
        
        if (n >= 2) {
            dp[2][1] = wine[2];
            dp[2][2] = wine[1] + wine[2];
        }
        
        for (int i = 3; i <= n; i++) {
            dp[i][1] = Math.max(dp[i - 2][1], dp[i - 2][2]);
            
            dp[i][2] = dp[i - 1][1];
        }

하지만 계단 오르기 문제와 다른 점은 1. 건너뛸 수 있는 수의 제한이 없다 2. 마지막 포도주를 꼭 마시지 않아도 된다가 있었다.

기존의 풀이에서는 dp[i][j]와 같이 dp 배열을 2차원으로 관리하면서 i번째 계단에서, j개를 연속으로 밟고 있음을 관리했다.

이러한 풀이를 이 문제에 적용할 경우 건너뛸 수 있는 포도잔의 수의 제한이 없기 때문에 i - 1, i - 2 뿐만 아니라 i - 3, i - 4... 등 그 이상을 모두 관리해야 한다.

따라서 dp 배열에서 몇 잔을 연속으로 마셨는지 관리하기 보단 최댓값 자체를 관리하는 것이 좋다고 생각했다.

      	int[] dp = new int[n + 1];
        
        dp[1] = wine[1];
        if (n >= 2) dp[2] = wine[1] + wine[2];
        
        for (int i = 3; i <= n; i++) {
            // 1. i번째는 안 마심 = dp[i - 1]이 최댓값일 것
            int case1 = dp[i - 1];
            
            // 2. i번째만 마심 = i-1번째는 안 마셨기 때문에 dp[i - 2]에 wine[i] 더함
            int case2 = dp[i - 2] + wine[i];
            
            // 3. i-1, i번째 마심 = i-2번째는 마실 수 없기 때문에 dp[i - 3]에 wine[i - 1], wine[i] 더함
            int case3 = dp[i - 3] + wine[i - 1] + wine[i];
            
            dp[i] = Math.max(case1, Math.max(case2, case3));
        }

dp 배열은 1차원으로 두어 i에서의 최댓값만 저장할 수 있도록 했다.

핵심 로직은 1. i번째는 안 마신다 2. i번째만 마신다(i-1번째는 안 마심) 3. i, i-1번째 마심로 3가지 케이스가 나올 수 있다.

1️⃣ i번째는 안 마실 경우

		// 1. i번째는 안 마심 = dp[i - 1]이 최댓값일 것
        int case1 = dp[i - 1];

i번째는 안 마신다는 것은 wine[i]의 값이 더해지면 안되고, 때문에 dp[i - 1]의 값이 최댓값이 될 것이다.

2️⃣ i번째만 마실 경우 = i-1번째는 안 마셨을 경우

		// 2. i번째만 마심 = i-1번째는 안 마셨기 때문에 dp[i - 2]에 wine[i] 더함
		int case2 = dp[i - 2] + wine[i];

i번째만 마신다는 것은 i - 1번째는 마시지 않았다는 것이고, dp[i - 2]의 값에 wine[i] 값을 더해주면 된다.

3️⃣ i, i-1번째를 마실 경우 = i-2번째는 마시면 안됨

		// 3. i-1, i번째 마심 = i-2번째는 마실 수 없기 때문에 dp[i - 3]에 wine[i - 1], wine[i] 더함
        int case3 = dp[i - 3] + wine[i - 1] + wine[i];

i, i-1번째를 마실 경우, 연속으로 3잔 이상은 마실 수 없으므로 i-2번째 포도주는 마시면 안된다.

따라서 dp[i - 3]의 값에 wine[i - 1], wine[i] 값을 더해주면 된다.

---

풀이

import java.io.*;

/* 계단 오르기 문제와 비슷.. 하지만 건너뛰는 포도주의 수에 제한이 없는 것이 다름
 * 
 * 처음 풀이 (계단 오르기 문제와 비슷하게)
 * - 연속 3잔 이상은 마실 수 없음
 * - 연속으로 마시는 포도주의 잔을 dp[i][1], dp[i][2]로 표시
 * - 이런 경우 3개, 4개.. 이상을 건너뛰는 경우를 표현할 수 없음
 * 
 * 최종 풀이
 * - 몇 잔을 연속으로 마셨는지 저장하지 말고 "최댓값"만을 관리하자
 * - i번째 잔에서 선택할 수 있는건 i번째 잔을 마시냐/안 마시냐
 */

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[] wine = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            wine[i] = Integer.parseInt(br.readLine());
        }
        
        int[] dp = new int[n + 1];
        
        dp[1] = wine[1];
        if (n >= 2) dp[2] = wine[1] + wine[2];
        
        for (int i = 3; i <= n; i++) {
            // 1. i번째는 안 마심 = dp[i - 1]이 최댓값일 것
            int case1 = dp[i - 1];
            
            // 2. i번째만 마심 = i-1번째는 안 마셨기 때문에 dp[i - 2]에 wine[i] 더함
            int case2 = dp[i - 2] + wine[i];
            
            // 3. i-1, i번째 마심 = i-2번째는 마실 수 없기 때문에 dp[i - 3]에 wine[i - 1], wine[i] 더함
            int case3 = dp[i - 3] + wine[i - 1] + wine[i];
            
            dp[i] = Math.max(case1, Math.max(case2, case3));
        }
        
        System.out.println(dp[n]);
    }
}