CS/PS

백준 2156 포도주 시식

kkumta 2021. 4. 30. 21:51

이 문제는 전형적인 DP 문제이다.

 

포도주가 3잔 놓여있다고 생각하자. 포도주를 마실 수 있는 경우의 수는 다음과 같다.

 

문제를 푸는 팁은 포도주는 최대 3개까지만 연속으로 마실 수 있기 때문에 점화식에서 d[i-1], d[i-2]+amount[i], d[i-3]+amount[i-1]+amount[i] 중 최댓값을 구하여 d[i]에 넣어주어야 한다는 것이다.

 

그래서 정답 코드는 다음과 같다.

 

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

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[] amount = new int[n + 1];
        int[] d = new int[n + 1];

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

        d[0] = 0;
        d[1] = amount[1];
        if (n >= 2) {
            d[2] = amount[1] + amount[2];
        }

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

        System.out.println(d[n]);

        br.close();
    }
}

 

난이도가 중하인 DP 문제는 알맞은 점화식을 찾는 것이 중요하다고 생각한다.

'CS > PS' 카테고리의 다른 글

최단 경로 알고리즘 정리  (0) 2022.08.28
Programmers: 큰 수 만들기  (0) 2022.08.11
[백준 11721] 열 개씩 끊어 출력하기 Java11  (0) 2021.01.08