[백준] 포도주 시식

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

 

 

문제에 나온 예시 입출력을 가지고 20분정도 고민해보니 규칙을 찾을 수 있었다.

길이가 n인 일차원 배열 wines에는 와인의 양을 저장한다.
길이가 n인 일차원 배열 dp에는 마실 수 있는 포도주의 최댓값을 저장한다.

포도주 잔이 k개 있는 경우(k>=3) 포도주를 마실 수 있는 경우의 수는 아래 중 최댓값이다.

1. k번째 포도주, k-1번째 포도주를 마시는 경우
   • 이 경우 최대값은 k번째 포도주 양 + k-1번째 포도주 양 + k-3번째까지 마신 포도주 최댓값
   • 즉, dp[k] = wines[k] + wines[k-1] + dp[k-3]
2. k번째 포도주, k-2번째 포도주를 마시는 경우
   • 이 경우 최대값은 k번째 포도주 양 + k-2번째까지 마신 포도주 최대값
   • 즉, dp[k] = wines[k] + dp[k-2]
3. k번째 포도주를 마시지 않는 경우
   • 이 경우 최대값은 k-1번째까지 마신 포도주 최대값
   • 즉, dp[k] = dp[k-1]

처음에는 DP 배열을 2차원으로 설정해 3가지 경우의 수를 모두 저장해가며 풀었다.
배열이 복잡한만큼 배열 초기화와 값설정을 잘못하여 자꾸 오답 판정을 받았다.
생각해보니 DP 배열은 일차원으로 설정하고, 위의 3가지 경우 중 최댓값만 저장하면 되는 것이었기에
DP배열을 일차원으로 바꿔 다시 풀었습다.

 

전체 코드

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

public class Main {
    public static void main(String[] args) {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            int n = Integer.parseInt(reader.readLine());
            int[] wines = new int[n];
            for (int i = 0; i < n; i++) {
                wines[i] = Integer.parseInt(reader.readLine());
            }
            if (n <= 2) {
                System.out.println(Arrays.stream(wines).sum());
                return;
            }

            int[] dp = new int[n];
            dp[0] = wines[0];
            dp[1] = wines[0] + wines[1];
            dp[2] = Math.max(dp[1], Math.max(wines[0] + wines[2], wines[1] + wines[2]));

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

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

        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}