[백준][2240번][DP] 자두나무

자두나무

https://www.acmicpc.net/problem/2240

<코드>

#include <stdio.h>
 
int max(int a, int b){
    return a > b ? a : b;
}
 
int main(void){
 
    int T, W;
    int Dp[2][1010][33] = {};
    int jado[1010] = {};
    int maxResult = 0;
    scanf("%d %d", &T, &W);
 
    for (int i = 1; i <= T; i++)
        scanf("%d", &jado[i]);
    
    for (int i = 1; i <= T; i++){
        for (int k = 0; k <= W; k++)
        {
            if (jado[i]==1)
            {
                
                Dp[0][i][k] = max(Dp[0][i][k], Dp[0][i - 1][k] + 1);
                Dp[0][i][k] = max(Dp[0][i][k], Dp[1][i - 1][k - 1] + 1);
                
        
                Dp[1][i][k] = max(Dp[1][i][k], Dp[1][i - 1][k]);
                Dp[1][i][k] = max(Dp[1][i][k], Dp[0][i - 1][k - 1]);
 
            }
            else
            {
                Dp[0][i][k] = max(Dp[0][i][k], Dp[0][i - 1][k]);
                Dp[0][i][k] = max(Dp[0][i][k], Dp[1][i - 1][k - 1]);
 
                Dp[1][i][k] = max(Dp[1][i][k], Dp[1][i - 1][k]+1);
                Dp[1][i][k] = max(Dp[1][i][k], Dp[0][i - 1][k - 1]+1);
            }
        }
        
 
    }
 
    for (int k = 0; k <= W; k++){
        maxResult = max(maxResult, Dp[0][T][k]);
        maxResult = max(maxResult, Dp[1][T][k]);
 
    }
 
    printf("%d\n", maxResult);
 
}

<문제 푼 요령>

1. 어떻게 DP 테이블을 짜느냐가 중요할 거 같은데 나는 DP[i][j][k] 로 테이블을 만들었다. i 는 0번인지 1번인지이고 j 는 j초에 떨어지는 자두 k 는 이동한 횟수라고 생각하고 테이블을 만들었다.

2. 자두나무 1에 오는 경우는 그대로 오는 경우와 그리고 자두나무 2에 있다가 오는 경우밖에없고 반대로 자두나무 2에 오는 경우는 자두나무 1에서 오는경우랑 그대로 있는 경우밖에없다. 대신에 나무를 이동할 때는 이동한 횟수인 k를 1 올려주면 된다.

3. 즉 2번의 경우로 테이블을 채워가는데 겹치는 경우는 max값만 채워 주면된다.

4. 마지막에 결과값은 K번째에 있는 testcase 에선 7번째에 있는 값들을 0~K 까지의 값들을 전부 비교해서 최대값을 뽑는 다면 그게 자두가 먹을 수 있는 최대 자두 갯수가 될 것이다.