[BOJ 2240] 자두나무

이 문제는,

 

 

 

 

 

 

위의 형태로 재귀적으로 호출할 수 있다. 메모이제이션을 통해서, 같은 반복문을 돌지 않도록 코드를 구성하면 된다.

 

 

 

 

주의할 점은, 문제의 조건에서 1번 나무에서 무조건 시작된다고 했으므로, 2번 나무로 시작할려면 W를 1 감소시키고 시작해야 한다.

 

 

 

 

해설코드(C++).

#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int T, W;
int arr[1001] = { 0 };
int dp[1001][31][3];
 
int func(int t, int w, int cur){
    if(dp[t][w][cur] != -1)
        return dp[t][w][cur];
        
    if(t == 0)
        return 0;
        
    dp[t][w][cur] = 0;
    if(cur == 1){
        if(arr[t] == cur){
            dp[t][w][cur] = 1 + func(t - 1, w, 1);
            if(w - 1 >= 0) dp[t][w][cur] = max(dp[t][w][cur], 1 + func(t - 1, w - 1 ,2));
        }else{
            dp[t][w][cur] = func(t - 1, w, 1);
            if(w - 1 >= 0) dp[t][w][cur] = max(dp[t][w][cur], func(t - 1, w - 1, 2));
        }
    }else{
        if(arr[t] == cur){
            dp[t][w][cur] = 1 + func(t - 1, w, 2);
            if(w - 1 >= 0) dp[t][w][cur] = max(dp[t][w][cur], 1 + func(t - 1, w - 1 ,1));
        }else{
            dp[t][w][cur] = func(t - 1, w, 2);
            if(w - 1 >= 0) dp[t][w][cur] = max(dp[t][w][cur], func(t - 1, w - 1 ,1));        
        }
    }
    
    return dp[t][w][cur];
}
 
int main() {
    cin >> T >> W;
    for(int i = 1; i <= T; i++){
        cin >> arr[i];
    }
    
    memset(dp, -1, sizeof(dp));
    cout << max(func(T, W, 1), func(T, W - 1, 2)) << endl; 
    
    return 0;
}