[알고리즘 / 백준] 2156 - 포도주 시식

www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

문제는 위와 같으며, 순서대로 해당 포도주를 마시는 경우, 아닌 경우 중 더 많이 마신 양을 저장하도록 하여 문제를 해결하였습니다.

 

1. n 번째 포도주를 마시는 경우는

(1) n - 1 번째 포도주를 안 마시는 경우: n - 2 번째 포도주까지 마신 최대 용량 + n 번째 포도주 양

(2) n - 2 번째 포도주를 안 마시는 경우: n - 3 번째 포도주까지 마신 최대 용량  + n - 1 번째 포도주 양 + n 번째 포도주 양

 

2. n 번째 포도주를 안 마시는 경우는

(3) n - 1 번째 포도주까지 마신 최대 양

 

따라서, n 번째 포도주 시식까지 마친 경우 마신 포도주의 최대 양은 (1), (2), (3) 중 최대 값이 됩니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin

n = int(stdin.readline())
wines = [int(stdin.readline()) for _ in range(n)]
dp = [0 for _ in range(n)]
dp[0] = wines[0]

if n > 1:
    dp[1] = wines[0] + wines[1]

if n > 2:
    dp[2] = max(dp[0] + wines[2], wines[1] + wines[2], dp[1])

for i in range(3, n):
    dp[i] = max(dp[i - 2] + wines[i], dp[i - 3] + wines[i - 1] + wines[i], dp[i - 1])

print(dp[-1])

 

자바 코드는 다음과 같습니다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[] dp = new int[n];
        dp[0] = wines[0];
        if (n > 1) {
            dp[1] = wines[0] + wines[1];
        }

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

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

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