백준 2156. 포도주 시식

문제 링크

난이도	정답률(_%)
Silver 1	34.330%

설계

• 총 포도주의 개수 N (<= 10,000)
• 이전 문제인 계단 오르기와 비슷하다. 연속 3개의 포도주를 시식할 수 없기 때문이다. 따라서 계단 오르기와 비슷하게 아래 두 개의 경우의 수를 갖는다.
  • n - 2번째 포도주를 마시고 n번째 포도주를 마신다.
  • n - 3번째, n - 1번째 포도주를 마시고 n번째 포도주를 마신다.
• 하지만 한가지 경우의 수가 더 필요한데, 계단 오르기는 연속으로 두 계단 이상을 넘어가지 못했던 반면, 포도주 시식은 마시지 않고 넘어가도 된다. 따라서 아래와 같은 경우의 수가 추가된다.
  • n번째 포도주를 마시지 않는다.

시간 복잡도

• O(N)

공간 복잡도

• 각 포도주의 양을 저장한 배열 wines N (<= 10,001)
• 포도주를 마셨을 때 최대 점수를 저장한 배열 drinks N (<= 10,001)

풀이

• 1, 2 잔을 마셨을 경우는 식이 다르므로 미리 최대값을 지정해준다.
  • 1: 1 번째
  • 2: 1 + 2 번째
• 3번째 잔부터는 마시지 않았을 경우(n-1), n-2를 마시고 마시는 경우, n-3, n-1을 마시고 마시는 경우 중 가장 많이 마셨을 경우를 저장해 출력한다.

결과

메모리	실행 시간
14920KB	104ms

코드

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

public class Main {
    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 wineNumber = Integer.parseInt(br.readLine());
        int[] wines = new int[10001];
        int[] drinks = new int[10001];

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

        drinks[1] = wines[1];
        drinks[2] = wines[1] + wines[2];

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

        bw.write(Integer.toString(drinks[wineNumber]));

        bw.flush();
        bw.close();
    }
}