BOJ 2240 : 자두나무

문제링크

풀이 요약

DP

풀이 상세

1. 자두를 받는 상황은 크게 6가지로 나눌 수 있다. (본래는 8가지이다. 단, 각 $n$번 자리에서 $n$번 나무의 사과를 안받는 경우는 이 문제에서는 존재하지 않으므로 6가지이다.)

   • 자두는 현재 1번에 있고, 1번 나무에서 떨어지는 사과를 받는다.
   • 자두는 현재 1번에 있고, 2번 나무에서 떨어지는 사과를 이동하여 받는다.
   • 자두는 현재 1번에 있고, 2번 나무에서 떨어지는 사과를 포기한다.
   • 자두는 현재 2번에 있고, 1번 나무에서 떨어지는 사과를 이동하여 받는다.
   • 자두는 현재 2번에 있고, 1번 나무에서 떨어지는 사과를 포기한다.
   • 자두는 현재 2번에 있고, 2번 나무에서 떨어지는 사과를 받는다.

2. 해당 식의 최적해는 자두가 이동해서 사과를 받는 경우와 받지 않는 경우 가운데 더 큰 값을 매초에 저장하여, 이동 상황 별 나타난 $T$ 초의 결과의 최댓값을 반환하는 것이다.

3. 문제에서 꼭 $W$ 씩 이동한다고는 말하지 않았다. 즉 테스트케이스 처럼 최대 2번 움직일 수 있지만, 1번 혹은 움직이지 않는 것에서 최대가 나올 수도 있으니 모든 이동 경우의 수를 비교해야한다.

#include <iostream>
using namespace std;
int T, W, a[1004], dp[3][1004][34], ans = -1;

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

void go() {
    dp[1][1][0] = a[1] == 1 ? 1 : 0;
    dp[2][1][1] = a[1] == 1 ? 0 : 1;
    
    for (int i = 2; i <= T; i++) {
        for (int j = 0; j <= W; j++) {
            if (a[i] == 1) {
                dp[1][i][j] = max(dp[1][i - 1][j], dp[2][i - 1][j - 1]) + 1;
                dp[2][i][j] = max(dp[1][i - 1][j - 1], dp[2][i - 1][j]);
            } else {
                dp[1][i][j] = max(dp[1][i - 1][j], dp[2][i - 1][j - 1]);
                dp[2][i][j] = max(dp[1][i - 1][j - 1], dp[2][i - 1][j]) + 1;
            }
        }
    }

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

void output() {
    cout << ans;
}

int main() {
    input();
    go();
    output();
}