2240 자두나무

백준 2240 자두나무 https://www.acmicpc.net/problem/2240

자두가 T초 동안 두개의 나무(1번나무, 2번나무)중 한곳에서 떨어지는데 주인공은 최대 M번움직이며 자두를 받을 수 있다. 이때의 받을 수 있는 자두의 최댓값을 구하는 문제이다.

간단한 예시를 가정하고 생각해보자. 표의 O는 해당 나무에서 n초에 자두가 떨어졌다는것을 의미한다.

T=1초 ,M=0번일때는 1번나무 그대로 서있기 때문에 자두 0개를 획득할 것이다.
T=1초, M=1번일때는 2번나무에서 자두 1개를 획득할 것이다.
1초에 2번이상은 자리를 바꿀 수 없으므로 N=1에서의 M은 1이 최대이다.

T=2초, M=0번일때는 자두 0개(1번,1번)
T=2초, M=1번일때는 자두 2개(1번,2번 or 2번,2번)
T=2초, M=2번일때는 자두 1개(2번,1번)
즉 T=2초 동안 최대 2번 움직일 수 있을 때 받을 수 있는 자두의 최대양은 2개가 되는것이다.

DP값을 다음과 같이 정의하였다.
DP[N][M] : M번 자리를 바꿨을 때 N초 동안 자두를 받을 수 있는 최대 양

앞의 예시를 보고 점화식을 유추할 수 도 있지만 사실 생각해보면 N초동안 M번 자리를 바꿨을 때의 자두 최댓값은 N초일때 자리를 바꿨을 때, 바꾸지 않았을 때로 나뉠 수 있다.

자리를 바꿨을 때의 이전경우의 최댓값은 DP[N-1][M-1]이 될것이고 바꾸지 않았을 때 이전경우의 최댓값은 DP[N-1][M]이 될 것이다.

이중 더 큰곳을 선택하여 N초일때 자두를 얻었는지 못얻었는지만 판별해 추가로 더해주면 된다. 이것을 점화식으로 풀어쓰면

DP[N][M] = max(DP[N-1][M-1], DP[N-1][M]) + plus

여기서 plus는 N초일때 자두를 얻었는지 여부에 대한 값을 더해주는 것이다.

이제 구현만 하면된다. 주의사항은 T에 따른 M의 범위를 생각해서 DP값에 저장시켜야한다.

#include <cstdio> #include <algorithm> using namespace std; int T[1001]; int dp[1001][31]; int main(){     int N, W, cnt = 0;     scanf("%d%d", &N, &W);     for (int n = 1; n <= N; n++){         scanf("%d", &T[n]);         if (T[n] == 1){             cnt++;             dp[n][0] = cnt;         }         else             dp[n][0] = cnt;     }     dp[1][1] = T[1] == 2 ? 1 : 0;     for (int n = 2; n <= N; n++){         for (int m = 1; m <= W; m++){             int plus;             if (n < m)                 continue;             if (m & 1)                 plus = T[n] == 2 ? 1 : 0;             else                 plus = T[n] == 1 ? 1 : 0;             dp[n][m] = max(dp[n - 1][m - 1], dp[n - 1][m]) + plus;             }     }     int ans = 0;     for (int m = 0; m <= W; m++)         ans = max(ans, dp[N][m]);     printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs