(10) [C++, Java] 백준 No.2156 : 포도주 시식

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-11-DP-문제-풀이10-백준-No2156-포도주-시식

 

# C++(Bottom-up방식 - 2차원 배열 사용)

#include <iostream>
#include <algorithm>

using namespace std;

int arr[10001];
int d[10001][3];


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> arr[i];
    
    d[1][1] = arr[1];           // 1잔만 있을 경우 최대 값은 1잔을 마시는 것이므로.
    
    d[2][0] = arr[1];           // 2잔만 있을 경우 2번째 자리의 상태가 S = 0인 경우의 최대값.
    d[2][1] = arr[2];           // 2잔만 있을 경우 2번째 자리의 상태가 S = 1인 경우의 최대값.
    d[2][2] = arr[1] + arr[2];  // 2잔만 있을 경우 2번째 자리의 상태가 S = 2인 경우의 최대값.

    for (int i = 3; i <=n; i++)
    {
        d[i][0] = max(max(d[i-1][0], d[i-1][1]), d[i-1][2]);
        d[i][1] = d[i-1][0] + arr[i];
        d[i][2] = d[i-1][1] + arr[i];
    }
    
    cout << max(max(d[n][0], d[n][1]), d[n][2]) << "\n";
}

# C++(Bottom-up방식 - 1차원 배열 사용)

#include <iostream>
#include <algorithm>

using namespace std;

int arr[10001];
int d[10001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> arr[i];
    
    d[1] = arr[1];           // 1잔이 있을 때 최대 값은 1잔을 마시는 것임
    d[2] = arr[1] + arr[2];  // 2잔이 있을 때 최대 값은 2잔을 모두 마시는 것임

    for (int i = 3; i <=n; i++)
        d[i] = max(max(d[i-1], d[i-2] + arr[i]), d[i-3] + arr[i-1] + arr[i]);
    
    cout << d[n] << "\n";
}

# Java

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n+1];
        for (int i=1; i<=n; i++) {
            a[i] = sc.nextInt();
        }
        int[] d = new int[n+1];
        d[1] = a[1];
        if (n >= 2) {
            d[2] = a[1]+a[2];
        }
        for (int i=3; i<=n; i++) {
            d[i] = d[i-1];
            d[i] = Math.max(d[i], d[i-2]+a[i]);
            d[i] = Math.max(d[i], d[i-3]+a[i-1]+a[i]);
        }
        int ans = d[1];
        for (int i=2; i<=n; i++) {
            ans = Math.max(ans, d[i]);
        }
        System.out.println(ans);
    }
}