문제 출처

단계별로 풀어보기 > 동적 계획법 1 > 포도주 시식
https://www.acmicpc.net/problem/2156

문제 설명

다음 규칙을 지켜서 마실 수 있는 포도주의 최대를 출력하라.
1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수 없다.

접근 방법

연속으로 놓여있는 포도주 3잔을 마시지만 않으면 되므로, 2칸 전과 3칸 전 + 1칸 전의 용량 + 현재 칸의 용량 을 비교하고, 이전 칸에 마신 포도주 용량과 비교한다.

import java.io.*;

public class 포도주_시식 {
    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());

        int arr[] = new int[n+1];
        int dp[] = new int[n+1];

        for(int i = 1; i < n+1; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

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


        bw.write(String.valueOf(dp[n]));
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

이전에 풀었던, 계단 오르기와 비슷하지만 세세한 부분이 달라서 조건이 달랐다.

시간 복잡도는 O(n)이다.

문제푼 흔적