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

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

 

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

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

---

1.  아이디어

 

다이나믹 프로그래밍을 활용하면 간단하게 해결할 수 있다.

---

2. 문제풀이

 

dp 배열에는 현재 잔까지 주어졌을 때 마실 수 있는 최댓값을 저장했다.

점화식은 현재 잔을 마시는 경우와 마시지 않는 경우 중 최댓값을 저장하고 현재 잔을 마시는 경우는 다시 3칸 왼쪽 잔을 마시고 1칸 왼쪽 잔을 마시고 현재 잔을 마시는 경우와 2칸 왼쪽 잔을 마시고 현재 잔을 마시는 경우 중 최댓값을 저장한다.

편의를 위해 배열에는 각각 앞쪽에 패딩을 해줬다.

---

3. 코드

 

import java.io.*;

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[3 + N];
        for (int i = 3; i < N + 3; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        int[] dp = new int[3 + N];
        for (int i = 3; i < N + 3; i++) {
            dp[i] = Math.max(Math.max(dp[i - 3] + arr[i - 1], dp[i - 2]) + arr[i], dp[i - 1]);
        }

        System.out.println(dp[N + 2]);
    }
}

---

4. 후기