[BOJ/백준][Gold5] 2240 : 자두나무 (C++)

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

2240번: 자두나무

 

 

[난이도] Gold5
[유형] DP

[풀이]
DP[t][w][k] : 현재 t초이며 w만큼 움직였고 k 위치에 있을 때 얻을 수 있는 최대 자두 개수.

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int T,W,a[1001],dp[1001][31][2];
int sol(int t,int w,int k){
    if(t>T) return 0;
    int& ret = dp[t][w][k];
    if(ret!=-1) return ret;
    ret = (k==a[t]) + sol(t+1,w,k);
    if(w<W) ret = max(ret,(k!=a[t]) + sol(t+1,w+1,!k));
    return ret;
}
int main(){
    scanf("%d%d",&T,&W);
    for(int i=1;i<=T;i++) {
        scanf("%d",&a[i]);
        a[i]--;
    }
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(1,0,0));
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2240.cpp