백준 2240 자두나무 (C++)

2240번: 자두나무

dp를 이용한 문제이다. 생각보다 까다로운 dp 문제였다. 두가지의 경우를 생각해봐야 한다. 이동을 했을 경우, 이동을 하지 않았을 경우. 먼저 시작 지점이 1번 나무이므로 첫 자두가 떨어지는 나무에 따라 dp의 처음 시작을 초기화해준다. 그리고 반복문을 돌면서 두가지 경우에 따라 dp를 구해주었다. 여기서 j=0 일 때 j-1에 접근을 하게 되는데 j에 해당하는 dp 배열의 크기를 32로 잡아주어 0이 나오도록 해주었다. 그 후 모든 이동 횟수와 나무의 최댓값을 구해 출력해주었다. 많이 까다로웠던 문제였다. dp문제를 좀 더 많이 풀어봐야겠다.

#include <iostream>
#include <algorithm>

using namespace std;

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

void solution() {
    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] = max(dp[i - 1][j][1], dp[i - 1][j - 1][2]) + (A[i] == 1);
            dp[i][j][2] = max(dp[i - 1][j - 1][1], dp[i - 1][j][2]) + (A[i] == 2);
        }
    }

    for (int i = 0; i <= W; i++) {
        for (int j = 1; j <= 2; j++) {
            result = max(dp[T][i][j], result);
        }
    }
    
    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];
    }

    solution();

    return 0;
}