[백준] 2240번 자두나무 C++

문제 출처: https://www.acmicpc.net/problem/2240

2240번: 자두나무

zadoo(현재 시간, 남은 움직임 횟수, 현재 위치)를 선언하여 Top-down방식으로 작성하였다.

 

함수가 호출되면

1. 가만히 있는다.

- 현재 위치에 자두가 떨어진다면 +1을 한다.

- 현재 위치에 자두가 떨어지지 않는다면 +0을한다.

 

2. 움직일수 있다면 움직여본다. (남은 움직임 횟수 -1)

- 현재 위치에 자두가 떨어진다면 +0을 한다.(움직인 곳에는 없기 때문에)

- 현재 위치에 자두가 떨어지지 않는다면 +1을 한다.(움직인 곳에 떨어지기 때문에)

 

각 조건에 대해 재귀적으로 호출한 뒤 최대값을 dp[현재시간][남은움직임횟수][현재위치]에 저장해두어 메모이제이션을 한다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <string>

using namespace std;

int T, W;
int arr[1001];
int dp[1001][31][2];

int zadoo(int idx, int move,int tree) {
    if (idx == T)return 0;
    if (dp[idx][move][tree] != -1)return dp[idx][move][tree];

    int val;
    if (arr[idx] == tree) val = zadoo(idx + 1, move, tree) + 1;
    else val = zadoo(idx + 1, move, tree);

    if (move > 0) {
        int nexttree = (tree == 1) ? 2 : 1;

        if (arr[idx] == tree) val = max(val, zadoo(idx + 1, move - 1, nexttree));
        else val = max(val, zadoo(idx + 1, move - 1, nexttree) + 1);
    }

    dp[idx][move][tree] = val;
    return val;
}


int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> T >> W;
    for (int i = 0; i < T; i++)cin >> arr[i];
    fill(&dp[0][0][0], &dp[1000][30][2], -1);


    cout << zadoo(0, W, 1);
    

}