문제

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

풀이

각 초마다 자리를 옮길지 말지 결정하여 자두를 최대로 받아야 한다. 여기서 중요하게 생각해야 할 부분은 최대로 움직일 수 있는 횟수(W)인데, 문제를 처음부터 차근차근 접근해보면 쉽게 풀 수 있다.

먼저 우리는 최대로 먹을 수 있는 경우를 구해야 한다. 이를 구하는 알고리즘을 재귀적으로 작성해보면 같은 경우를 여러번 계산 하는 경우를 발견할 수 있는데 이를 방지하기 위해 메모이제이션을 적용해야한다.

메모이제이션 할 배열 을 dp[sec][rest]로 했을때 dp[sec][rest] = sec초에 rest번 더 움직일수 있는 경우에서 자두를 받을 수 있는 최대 개수가 된다. 메모리 제한이 128MB이므로 1000 * 31만큼 잡아줘도 메모리 제한에 걸릴 일은 없다.

여기서 우리는 가장 처음에 몇 번 먹을지 쉽게 미리 구할 수 있다. 자두는 처음 1번 나무 밑에 있는데, W가 1 이상이라면 시작하자마자 한번 또는 그 이상 움직여서 2번 나무에서 시작 할 수 있는 경우가 있다. 즉 dp[0][rest]에서 rest가 W - (2 * x)인 경우는 모두 값이 같으며 dp[0][rest]에서 rest가 W - 1 - (2 * x)인 경우 역시 모두 값이 같은데 이 경우 전자는 처음에 자두가 1번 나무에서 떨어질때 1, 후자는 처음에 자두가 2번 나무에서 떨어질때 1로 초기화 해주면 된다.

그 후 두가지 경우의 수에 따라 T * W번 반복을 하며 답을 구해주면 되는데, 만약 dp[sec][rest]를 구할 때 rest가 W랑 같다면, 즉 한번도 움직이지 않았다면 고려할 수 있는 경우가 이전까지도 한번도 움직지이 않은 경우 dp[sec - 1][rest] 밖에 없으므로 dp[sec][rest] = dp[sec - 1][rest] + sec초에 자두가 지금 서있는 나무에서 떨어지는가?만 계산하면 된다. 만약 한번 이상 움직였다면 dp[sec][rest] = max(dp[sec - 1][rest], dp[sec - 1][rest - 1]) + sec초에 자두가 지금 서있는 나무에서 떨어지는가?가 된다. 왜냐하면 이번에 움직였을 경우를 같이 고려해야 되기 때문에 두 값 중 최대값을 구하고 그 값에 현재 위치에서 자두를 받을 수 있는가를 구하면 항상 최대로 받을 수 있는 경우를 따라가기 때문이다.

이후 모든 경우를 다 구한 뒤 dp[T-1][0] ~ dp[T-1][W]중 최대값을 출력해주면 된다.

코드

#include <cstdio>
int drop[1000], dp[1000][31];
int max(int x, int y) { return x > y ? x : y; }
int main() {
    int i, j, T, W, ret = 0;
    scanf("%d%d", &T, &W);
    for (i = 0; i<T; i++)
        scanf("%d", drop + i);
    for (i = 0; i<=W; i++)
        dp[0][i] = (drop[0] == ((i % 2) + 1));
    for (i = 1; i<T; i++) {
        for (j = W; j>=0; j--) {
            if (j == W)
                dp[i][j] = dp[i - 1][j] + (drop[i] == ((j % 2) + 1));
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j + 1]) + (drop[i] == ((j % 2) + 1));
        }
    }
    for (i = 0; i<=W; i++) {
        ret = max(ret, dp[T - 1][i]);
    }
    printf("%d", ret);
}