BOJ 2240번 자두나무

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

 

처음에는 solve(1번 나무,,) , solve(2번 나무..) 로 둘중에서 큰값을 선택하는 식으로 풀었는데

계속 WA가 뜨길래 어떤 문제점이 있는건지 도통 알수가없어서 포기했다.

몇일뒤에 다시 풀려고 문제를 천천히 읽어봤는데

자두는 1번나무 아래에 위치해 있다는 글을 읽었다..

그래서 solve(1번나무)만 구하니 AC를 받게 되었다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 
int T, W;
int fall[1001];
int dp[3][1002][32];
 
int solve(int tree, int falling, int moving) {
    if (falling < 0 || moving < 0) return 0;
    
    int& res = dp[tree][falling][moving];
    if (res != -1) return res;
 
    res = 0;
    if (tree == fall[falling]) res++;
    res += max(solve(tree, falling - 1, moving), solve(tree == 1 ? 2 : 1, falling - 1, moving - 1));
 
    return res;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    
    cin >> T >> W;
    for (int i = 0; i < T; i++) {
        cin >> fall[i];
    }
    memset(dp, -1, sizeof(dp));
    cout << solve(1, T, W);
 
    return 0;
}