BOJ 2240: 자두나무 (c++)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int T, W;
int arr[1001];
int dp[1001][31][2]; // [시간][이동횟수][위치(0:1번, 1:2번)]

int go(int time, int move, int pos) {
    // 기저 조건: 시간이 끝났다면 자두 못 받음
    if (time > T) return 0;

    // 메모이제이션 되어 있다면 반환
    int &ret = dp[time][move][pos];
    if (ret != -1) return ret;

    ret = 0;

    // 현재 위치에서 자두를 받을 수 있는 경우
    int get = (arr[time] == pos + 1) ? 1 : 0;

    // 1. 현재 위치 유지
    ret = max(ret, go(time + 1, move, pos) + get);

    // 2. 다른 위치로 이동 (이동 가능할 때만)
    if (move < W) {
        ret = max(ret, go(time + 1, move + 1, 1 - pos) + ((arr[time] == (2 - pos)) ? 1 : 0));
    }

    return ret;
}

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

    cin >> T >> W;
    for (int i = 1; i <= T; ++i) {
        cin >> arr[i];
    }

    memset(dp, -1, sizeof(dp));

    // 시작은 1번 나무(=0번 인덱스), 이동 없이 시작
    cout << go(1, 0, 0) << '\n';

    return 0;
}

bottom up DP로 풀 수 있다.

시간, 이동횟수, 위치 총 3차원 배열 필요