[BOJ][2156] 포도주 시식

1. 문제 링크

https://www.acmicpc.net/problem/2156

2. 사용 알고리즘

DP

3. 풀이

d[n][a] : n번째 포도주까지 마셨을 때 최대값, a는 n번째 포도주가 몇 번 연속인지

• 0번 연속 : d[n][0] = max(d[n - 1][0], d[n - 1][1], d[n - 1][2])

• 1번 연속 : d[n][1] = d[n - 1][0] + p[n]

• 2번 연속 : d[n][2] = d[n - 1][1] + p[n]

∴ max(d[n][0], d[n][1], d[n][2])

4. 소스 코드

4-1. C++

4-1-1. Top-Down

https://github.com/dev-aiden/problem-solving/blob/main/boj/2156.cpp

#include <iostream>

using namespace std;

int d[10003][3];
int arr[10003];

int solve(int n, int a) {
    if (n == 0) return 0;
    if (d[n][a] != -1) return d[n][a];
    if (a == 0) d[n][a] = max(max(solve(n - 1, 0), solve(n - 1, 1)), solve(n - 1, 2));
    else if (a == 1) d[n][a] = solve(n - 1, 0) + arr[n];
    else if (a == 2) d[n][a] = solve(n - 1, 1) + arr[n];
    return d[n][a];
}

int main(void) {
    ios_base::sync_with_stdio(false);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 3; ++j) d[i][j] = -1;
        cin >> arr[i];
    }
    for (int i = 0; i < 3; ++i) solve(n, i);
    cout << max(max(d[n][0], d[n][1]), d[n][2]) << "\n";
    return 0;
}

4-1-2. Bottom-Up

https://github.com/dev-aiden/problem-solving/blob/main/boj/2156_2.cpp

#include <iostream>

using namespace std;

int d[10003][3];
int arr[10003];

int main(void) {
    ios_base::sync_with_stdio(false);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    for (int i = 1; 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";
    return 0;
}

4-2. JAVA

4-2-1. Top-Down

https://github.com/dev-aiden/problem-solving/blob/main/boj/2156.java

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

import static java.lang.Math.max;

public class Main {

    static int d[][] = new int[10003][3];
    static int arr[] = new int[10003];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i = 1; i <= n; ++i) {
            for(int j = 0; j < 3; ++j) d[i][j] = -1;
            arr[i] = Integer.parseInt(br.readLine());
        }
        for(int i = 0; i < 3; ++i) solve(n, i);
        System.out.println(max(max(d[n][0], d[n][1]), d[n][2]));
    }

    public static int solve(int n, int a) {
        if(n == 0) return 0;
        if(d[n][a] != -1) return d[n][a];
        if(a == 0) d[n][a] = max(max(solve(n - 1, 0), solve(n - 1, 1)), solve(n - 1, 2));
        else if(a == 1) d[n][a] = solve(n - 1, 0) + arr[n];
        else if(a == 2) d[n][a] = solve(n - 1, 1) + arr[n];
        return d[n][a];
    }
}

4-2-2. Bottom-Up

https://github.com/dev-aiden/problem-solving/blob/main/boj/2156_2.java

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

import static java.lang.Math.max;

public class Main {

    static int d[][] = new int[10003][3];
    static int arr[] = new int[10003];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i = 1; i <= n; ++i) arr[i] = Integer.parseInt(br.readLine());
        for(int i = 1; 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];
        }
        System.out.println(max(max(d[n][0], d[n][1]), d[n][2]));
    }
}