(C++) - 백준(BOJ) 14720번 : 우유축제 답

www.acmicpc.net/problem/14720

14720번: 우유 축제

dp문제였습니다

 

풀이방법

d[n][k] : 위치 n에서 k종류의 우유를 마셨을 때 최대 마신 우유 개수

답 : max(만약 현재위치 n에서 k종류를 마실 차례가 되었다면 그 우유를 마셨을 때 개수, 현재 위치 우유를 마시지 않았을때의 우유 개수)

 

Code

#include <bits/stdc++.h>
using namespace std;
int num, n;
int d[1000][3];
int milk[1000];
int dp(int n,int k){
    int &ret = d[n][k];
    if(ret!=-1) return ret;
    if(n==num) return 0;
    if(milk[n] == k) ret = dp(n+1,(k+1)%3) + 1;
    ret = max(ret, dp(n+1,k));
    return ret;
}
int main(){
    cin >> n;
    num = n;
    for(int i = 0; i < n; i++){
        cin >> milk[i];
    }
    memset(d,-1,sizeof(d));
    cout << dp(0,0);
}