백준 2156번 : 포도주 시식 자바

🧫 문제 분석

 

✔️ 출처

포도주 시식 실버 1

 

📖 문제

 

동적 프로그래밍 문제이다. 

 

문제를 보면

1. 선택한 잔은 모두 마시고 원위치

2. 연속으로 3잔 마시기 불가능

 

i = 3 부터 시작 

1. 현재 잔 + dp[i - 2]

2. 현재 잔 + 이전 잔 + dp[i - 3]

3. dp[i - 1]    // 이전까지의 최댓값을 가진다. 

 

이 세가지 중 max값을 찾으면 된다. 

 

 

 

1. 현재 잔 + dp[i - 2]

2잔을 마시고 한 칸 뛰고 한 잔을 마신 경우이다. 

 

1 2 3 번째 잔을 연속해서 마실 수 없으므로 

dp[1]의 값 즉, 0과 1 번째 잔을 마신 최댓값 을 더한다.

 

 

2. 현재 잔 + 이전 잔 + dp[i - 3]

 

한 잔을 마시고 한 칸 뛰고 연속으로 2잔을 마신 경우이다.

dp[0] 잔까지 마시고 1번째 잔을 건너 뛰고 2번째 3번째 잔을 마신다. 

 

3. dp[i - 1]

dp[i-1] 에는 이전 잔까지의 최댓값을 가진다. 

1, 2번째 경우보다 이전 dp의 마신 양이 더 클 경우가 있기도 하고

현재 dp[i] 값을 구하는 것은 결국 현재 잔까지의 최댓값을 구하는 것이기 때문이다.

 

---

🔅 문제 풀이

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

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[] arr = new int[n];
        int[] dp = new int[n + 1];

        // 포도주 테이블 초기화
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        if (n < 2) {
            System.out.println(arr[0]);
            return;
        }

        dp[1] = arr[0];
        dp[2] = arr[0] + arr[1];

		// for문은 포도주 테이블을 기준으로 i를 설정하였다. 
        for (int i = 2; i < n; i++) {
            int cur = arr[i];
            int pre = arr[i - 1];
            int index = i + 1; // dp는 사실상 1부터 시작이므로  i + 1 을 해주어 포도주와 맞춘다.

            dp[index] = Math.max(dp[index - 1],
                    Math.max(dp[index - 2] + cur, dp[index - 3] + cur + pre));
        }

        System.out.println(dp[n]);
    }

}

 

 

 

❗ 오답노트 / 필요한 지식

1. 나름 빠르게 dp 문제를 풀었다.