[BaekJoon][2240] 자두나무

BAEKJOON ONLINE JUDGE

2240 자두나무

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

DP

처음에 bottom-up으로 접근했다가 틀려서

일단 top-down으로 먼저 풀음

어떤 시간에 어떤 나무에 있을 경우에는 이전에 같은 나무에 있었다가 그대로 기다린 경우, 이전에 다른 나무에 있었다가 옮겨서 지금의 나무에 있는 경우가 존재하므로 이 둘 중에 큰 값을 가져와야 한다. 그리고 지금 있는 나무의 위치에서 자두가 떨어지면 +1, 아니면 그냥 있는 걸로

#include <stdio.h>
#include <string.h>
 
#define Max(x, y)        (((x) > (y)) ? (x) : (y))
 
int t, w;
int dp[1001][33][2];
int tree[1001];
 
int solve(int time, int cnt, int tr)
{
    int value = 0;
 
    if (tree[time] == tr)    value = 1;
    if (time > t || cnt > w)        return 0;
    if (dp[time][cnt][tr] != -1)    return dp[time][cnt][tr];
    
    dp[time][cnt][tr] = Max(solve(time + 1, cnt, tr), solve(time + 1, cnt + 1, !tr)) + value;
 
    return dp[time][cnt][tr];
}
 
int main()
{
    int i, j;
    int max = 0;
 
    scanf("%d %d", &t, &w);
 
    for (i = 1; i <= t; i++) {
        scanf("%d", &tree[i]);
        tree[i]--;
    }
 
    memset(dp, -1, sizeof(dp));
 
    tree[0] = 1;
    printf("%d\n", solve(0, 0, 0));
 
    return 0;
}

다시 bottom-up으로 접근

나무값을 입력 받으면서 값을 갱신

dp[이동 횟수][있는 위치 (나무 번호)]

한번도 이동하지 않을 경우에 현재 있는 나무에서 자두가 떨어지면 +1

이동하는 경우에는 자두가 떨어지는 나무로 이동하는 것과 아닌 나무로 이동하는 2가지 모두 갱신해야 한다.

아닌 나무로도 이동을 해야 그 값을 나중에 계산할 때 쓴다.

#include <stdio.h>
 
#define Max(x, y)        (((x) > (y)) ? (x) : (y))
 
int time, w;
int dp[31][2];
 
int main()
{
    int i, j;
    int tree, max = 0;
 
    scanf("%d %d", &time, &w);
 
    for (i = 0; i < time; i++) {
        scanf("%d", &tree);
        tree--;
 
        dp[0][tree]++;
        for (j = 1; j <= w; j++) {
            dp[j][tree] = Max(dp[j][tree], dp[j - 1][!tree]) + 1;
            dp[j][!tree] = Max(dp[j][!tree], dp[j - 1][tree]);
        }
    }
 
    for (i = 0; i <= w; i++) {
        max = Max(Max(dp[i][0], dp[i][1]), max);
    }
 
    printf("%d\n", max);
 
    return 0;
}