2156 포도주 시식

BOJ::2156 포도주 시식

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

dp 문제이다.

N번째 경우에 대해 점화식을 세우기 위해 2차원 배열을 만들었다.

ㅁㅁㅁ ...... ㅁ

 1 2 3       N

N번째에 올수 있는 경우 3가지

1)N번째에 포도주를 연속으로 0번째 먹는 경우

2)N번째에 포도주를 연속으로 1번째 먹는 경우

3)N번째에 포도주를 연속으로 2번째 먹는 경우

각 경우에 대한 점화식

d[n][0] = max(d[i-1][0],d[i-1][1],d[i-1][2])

d[n][1] = a[i] + d[i-1][0];

d[n][2] = a[i] + d[i-1][1];

<JAVA>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    static int a[]=new int[10001];
    static int d[][]=new int[10001][3];
    static int n;
    public static void main(String args[]) throws NumberFormatException, IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(br.readLine());
        
        for(int i = 1 ; i<= n; i++){
            a[i]=Integer.parseInt(br.readLine());
        }
        
        d[1][1]=a[1];
        
        for(int i = 2 ; i<= n ;i++){
            d[i][0]=Math.max(d[i-1][0], Math.max(d[i-1][1], d[i-1][2]));
            d[i][1]=a[i]+d[i-1][0];
            d[i][2]=a[i]+d[i-1][1];
        }
        
        System.out.println(Math.max(d[n][0], Math.max(d[n][1], d[n][2])));
    }
}

<C++>

#include <iostream>
using namespace std;
 
int n;
int d[10001][3];
int a[10001];
 
int max(int a,int b) {
    if (a > b) {
        return a;
    }
    return b;
}
 
int main() {
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    //첫번째 잔을 먹는경우에 대한 초기화
    //0잔을 먹는경우 = 0, 2잔을먹는경우 불가능 이므로 초기화 할 필요 x
    d[1][1] = a[1];
 
    for (int i = 2; i <= n; i++) {
        d[i][0] = max(d[i - 1][0], max(d[i - 1][1], d[i - 1][2]));
        d[i][1] = a[i] + d[i - 1][0];
        d[i][2] = a[i] + d[i - 1][1];
    }
 
    int res = max(d[n][0], max(d[n][1], d[n][2]));
    cout << res << endl;
}