문제

BOJ 2156: 포도주 시식 https://www.acmicpc.net/problem/2156

풀이

조건

• 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
• 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
• 최대로 마실 수 있는 포도주의 양을 구한다.

풀이 순서

• 1번째는 1번째 잔을 마신 경우 최대가 된다.
• 2번째는 1번째와 2번째 잔을 마신 경우 최대가 된다.
  • 인덱스 에러가 나지 않도록 조건문으로 처리한다.
• i 번째 잔을 마실 때의 최대값을 구한다.
  • i번째와 i-2번째 까지 마신 값
  • i번째와 i-1번째, i-3번째 까지 마신 값
  • i번째를 마시지 않은 값
  • 위의 3개의 경우 중 최대 값을 구한다.

코드

Java

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

        long[] dp = new long[10010];

        // 1번째는 1번째 잔을 마신 경우 최대
        dp[1] = arr[1];
        // 2번째는 1번째와 2번째 잔을 마신 경우 최대 -> 인덱스 에러 안나도록 조건문으로 처리
        if (N > 1) {
            dp[2] = arr[1] + arr[2];
        }
        // i 번째의 최대 구하기
        for (int i = 3; i <= N; i++) {
            dp[i] = Math.max(dp[i-1], Math.max(arr[i] + dp[i - 2], arr[i] + arr[i - 1] + dp[i - 3]));
        }

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

}

정리

• dp[2] 를 구할 때 인덱스 에러 처리를 못해줘서 틀렸었다.
• i번째 와인을 마시지 않아도 되는 경우를 처리하지 못해서 틀렸었다.