[백준 JAVA] 2156 : 포도주 시식

[백준 2156] 포도주 시식 : https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

---

문제 조건 정리

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. -> 연속으로 2잔까지 마실 수 있다.
3. 될 수 있는 대로 많은 양의 포도주를 마셔야한다.

---

입력

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

---

문제를 풀기 전

 

• 계단 오르기 문제와 비슷하다고 생각함!
• 해당 문제는 마지막 와인이 포함되어야 한다는 조건이 없는 것을 확인함!

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

• "또 DP구나" 생각함!

---

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());

        int[][] dp = new int[n + 1][3];
        // dp[x][0] -> x번째 차례에 마시지 않겠다.
        // dp[x][1] -> x번째 차례에 마시지만 직전에는 마시지 않았다.
        // dp[x][2] -> x번째 차례에 마시고, 직전에도 마셨다.
        
        int podoju; // 포도주의 양
        
        // 아래 반복문에서 인덱스를 벗어나는 것을 피하기 위한 dp[1]을 직접 선언
        podoju= Integer.parseInt(bufferedReader.readLine());
        dp[1][0] = 0; // 선언하지 않아도 무방
        dp[1][1] = podoju; // 선언해야함
        dp[1][2] = 0; // 선언하지 않아도 무방

        for (int i = 2; i <= n; i++) {
            podoju = Integer.parseInt(bufferedReader.readLine());
            
            // MAX(직전에 마시지 않은 경우, 직전에 마신 경우, 전전과 직전에 마신 경우) 
            dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1], dp[i - 1][2]));
            
            // 직전에 마시지 않은 경우 + 이번에 마시기
            dp[i][1] = dp[i - 1][0] + podoju;
            
            //    직전에 마신 경우   + 이번에 마시기
            dp[i][2] = dp[i - 1][1] + podoju;
        }

		// 마지막 단계에서의 최대값 출력
        System.out.println(Math.max(dp[n][2], Math.max(dp[n][0], dp[n][1])));
    }
}

 

---

문제를 풀고 난 후

 

위 풀이는 dp 배열을 2차원으로 선언했으나, 포도주 입력을 배열로 저장한 후, dp 배열을 1차원으로 풀이된 것을 다른 분이 작성하신 포스팅으로 확인했다.

 

여러 방법이 있는 문제라고 생각함!