점화식을 생각해내지 못해 풀이를 찾아보고 해결하였다. 출처

처음에는 각 DP Index에 TREE라는 Struct를 만들어 해결하고자 하였는데 이러면 같은 Index에 위치를 옮겼는지, 옮기지 않았는지에 대한 결과가 max값으로 저장된다. 하지만 이렇게 되면 후반으로 갈 수록 정답이 아닐거 같다는 생각에 바로 포기하고 다른 방식을 생각해보았지만 결국 답을 생각해 내지 못했다.

풀이에서는 [시간][이동횟수][나무위치]로 표시한 3차원 배열을 통해 이 문제를 해결했다.
그런데 풀이에서는 이전 이동한 값을 참고하기 위해 j-1로 접근하였는데 j가 0일 때 아무런 조건 없이 j-1을 접근하는거 같아 문제를 풀때 j가 0이상 일때만 접근하라는 조건을 달아 해결하였다.

정답

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int T, W, result = 0;
int A[1001];
int dp[1001][32][3];

void solve() {
    dp[1][0][1] = A[1] == 1;
    dp[1][1][2] = A[1] == 2;

    for (int i = 2; i <= T; i++) {
        for (int j = 0; j <= W; j++) {
            dp[i][j][1] = dp[i - 1][j][1] + (A[i] == 1);
            if (j > 0) {
                dp[i][j][1] = max(dp[i][j][1], (dp[i][j - 1][2] + (A[i] == 1)));
            }
            dp[i][j][2] = dp[i - 1][j][2] + (A[i] == 2);
            if (j > 0) {
                dp[i][j][2] = max(dp[i][j][2], (dp[i][j - 1][1] + (A[i] == 2)));
            }
        }
    }

    for (int i = 1; i <= 2; i++) {
        for (int j = 0; j <= W; j++) {
            result = max(result, dp[T][j][i]);
        }
    }

    cout << result;

}

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

    cin >> T >> W;

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

    solve();

    return 0;
}