[백준] 2240번 자두나무

[적용한 알고리즘]

DP

 

[아이디어]

DP[지난 시간][이동한 횟수][현재 있는 나무]

그리고 자두가 떨어지는 위치를 입력한 배열을 a[] 라고 했을 때,

 

현재 시간을 i,

움직인 횟수를 j,

현재 있는 나무가 1번 혹은 2번 이면,

 

1. a[i] = 1 인 경우

1-1) 1번 나무에 위치한 경우 (받아먹는 경우)

dp[i][j][1] = max(받아먹기 위해 2번에서 이동한 경우, 그대로 1번에 있던 경우) + 1 

102) 2번 나무에 위치한 경우 (이번엔 받아먹지 않기로 한 경우)

dp[i][j][2] = dp[i - 1][j][2]

 

2. a[i] = 2 인 경우

2-1) 2번 나무에 위치한 경우 (받아먹는 경우)

dp[i][j][2] = max(받아먹기 위해 1번에서 이동한 경우, 그대로 1번에 있던 경우) + 1

2-2) 1번 나무에 위치한 경우 (이번엔 받아먹지 않기로 한 경우)

dp[i][j][1] = dp[i - 1][j][1]

 

[교훈]

여기서 반드시 신경 써줘야하는 경우가 j = 0 (한번도 안움직이는 경우) 이다.

j - 1 이 음수가 되는 경우를 (j = 0) 신경안써주고 코드 썼다가 피똥쌌다.

j = 0 인 경우도 분류 해줘야한다.

 

찾는데 한참 걸렸다..

 

<코드>

#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
    int T, W;
    scanf("%d %d", &T, &W);

    int a[1001];
    for (int i = 1; i <= T; i++){
        scanf("%d", &a[i]);
    }

    int dp[1001][31][3] = { 0 };
    if (a[1] == 1) dp[1][0][1] = 1;
    if (a[1] == 2) dp[1][1][2] = 1;

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

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

    printf("%d", ans);

    return 0;
}