[Java] 2156. 포도주 시식

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

문제 분석 과정

• 이전에 두 잔을 연속으로 마셨다면 그 다음 잔은 마실 수 없습니다.
• 최대 이전 3개의 값들까지만 기억하면 된다는 점을 이용해서 공간 최적화를 할 수 있습니다.

 

점화식

• dp[i−1]: 현재 잔 ii를 마시지 않고 이전 최적해를 그대로 가져오는 경우.
• dp[i−2]+array[i]: 이전 잔은 건너뛰고 현재 잔을 마시는 경우.
• dp[i−3]+array[i−1]+array[i]: 이전 잔과 현재 잔을 마시되, 두 칸 떨어진 잔은 건너뛰는 경우.

 

• dp[i]=max⁡(dp[i−1],dp[i−2]+array[i],dp[i−3]+array[i−1]+array[i])

• 초기값 설정
  • dp[0]=array[0]: 첫 번째 잔을 마시는 경우.
  • dp[1]=array[0]+array[1]dp[1]=array[0]+array[1]: 첫 번째와 두 번째 잔을 모두 마시는 경우.
  • dp[2]=max⁡(dp[1],array[0]+array[2],array[1]+array[2]): 세 번째 잔까지의 최적해.

 

 

코드

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

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

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

        if (n == 1) {
            System.out.println(array[0]);
            return;
        }

        dp[0] = array[0];
        dp[1] = array[0] + array[1];
        if (n > 2) {
            dp[2] = Math.max(dp[1], Math.max(array[0] + array[2], array[1] + array[2]));
        }

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

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

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[] array = new int[n];

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

        if (n == 1) {
            System.out.println(array[0]);
            return;
        }

        if (n == 2) {
            System.out.println(array[0] + array[1]);
            return;
        }

        int prev3 = array[0];
        int prev2 = array[0] + array[1];
        int prev1 = Math.max(prev2, Math.max(array[0] + array[2], array[1] + array[2]));

        for (int i = 3; i < n; i++) {
            int current = Math.max(prev1,
                    Math.max(prev2 + array[i], prev3 + array[i - 1] + array[i]));
            prev3 = prev2;
            prev2 = prev1;
            prev1 = current;
        }

        System.out.println(prev1);
    }
}

n을 기반으로 배열을 생성하였을 때는 n의 값에 따라 배열의 1, 2번 인덱스에 접근할 수 없을 수 도 있기에 (Out of bound) 이를 따로 처리해주어야 합니다.