Backjoon(백준) 2156번 - 포도주 시식(Java)

1. 풀이 힌트 

 - 현재 인덱스에서 어떻게 와인을 먹어야 최대 값이 나올 수 있는지 케이스를 나눈 후 각 케이스중에 최대 값을 구한다

2. 풀이 과정

 - 잔이 1개라면 현재 마실 수 있는 최대 양이다.

 - 잔이 2개라면 현재 마실 수 있는 최대 양은 두 잔을 더한 값이다.

 - 잔이 3개 이상이라면 연속해서 3잔 이상을 마실 수 없으므로 조건을 고려하여 현재 인덱스에서 마실 수 있는 최대의 양을 계산해야 한다. 최대 값이 나올 수 있는 케이스는 3가지가 있다

 1) dp[i] = dp[i - 1] 

  - dp[i]를 현재 인덱스(i)에서 마실 수 있는 최대 와인의 양이라고 했을 때, dp[i]는 dp[i - 1]가 되는 케이스이다. 예를 들어 각각 용량이 40, 50, 1인 와인잔이 있을 때 왼쪽부터 순서대로 마셔야 하고, 세 잔을 연속으로 마실 수 없으므로 현재 인덱스 3에서 마일 수 있는 최대의 양은 40 + 50 즉, 인덱스가 2일 때의 최대 값과 같다.

 2) dp[i] = dp[i - 2] + wine[i] : wine[i]을 마지막 와인잔의 양이라고 했을 때, wine[i]을 선택하고, 최대 값을 구할 수 있는 경우는 2가지가 있다 첫 번째는, wine[i - 1]을 건너 뛰고 wine[i - 2]까지의 최대 양인 dp[i -2]를 더하는 것이다.

 3) dp[i] = dp[i - 3] + wine[i] + wine[i - 1] : 마지막 와인잔을 선택했을 때 최대 값을 구할 수 있는 2번 째 방법은 wine[i]과 wine[i - 1]을 선택하고 조건에 의해 wine[i - 2]의 값은 건너 뛴 뒤에 dp[i - 3]의 값(wine[i - 3]까지의 마실 수 있는 최대양)을 더하는 것이다

 - 위의 3가지 케이스를 비교하여 최대 값을 구한 뒤 출력하면 정답이다.

3. 코드 구현

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

public class WineTasting {
    
    static int[] wine = new int[10001]; // 와인의 양을 저장을 저장하는 배열 
    static int[] dp = new int[10001]; // 마실수 있는 최대 와인의 양을 저장하는 배열
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine()); // 잔의 개수 
        
        for (int i = 1; i <= n; i++) { // 배열에 와인 저장
            int c = Integer.parseInt(br.readLine());
            wine[i] = c; 
        }
        
        dp[1] = wine[1]; // 와인이 1잔이면 최대 양은 1잔
        dp[2] = wine[1] + wine[2]; // 와인이 2잔이면 최대양은 2잔을 더한 값
        
        // 3잔 부터는 문제의 조건에 맞추어 계산해야 함
        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max((dp[i - 3] + wine[i - 1] + wine[i]), (dp[i - 2] + wine[i]));
            dp[i] = Math.max(dp[i], dp[i - 1]);
        }
        System.out.println(dp[n]);

    }

}

 

* 문제 링크

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