2240번

2240번 - 자두나무

이 문제를 재귀로 풀었는데, 처음에는 뒤에서부터 줄여오는 방식으로 문제를 풀었다.

그러다보니 생기는 문제가, 처음에 시작점이 1이라는 것. 나는 이점을 어떻게 해야할 지 잘 모르겠다...

(방법 해결 - 아래 코드로 추가)

그래서 아예 시작점에서부터 커지는 재귀, 마치 iterative DP 모양으로 문제를 풀었다.

그 다음 중요한 점은 정답을 구할 때, max(go(0, 0, 1),go(0,1,2)) 이런 형식으로 정답을 구해야 했다.

0초인 움직일 수 있기 때문이다.

D[t][w][now] = t 초에 w번 움직이고, 현재 위치가 now 일 때, 먹은 자두의 최댓값

움직일 때와 움직이지 않을 때로 구해주고, 이럴 때 현재 자두를 먹을 수 있으면 1을 더해주는 방식으로 코드를 짰다.

<정답 코드 -앞에서 뒤로 iterative DP 재귀>

#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
vector<int> v;
int D[1001][31][2];
int T, W;
int go(int t, int w, int now)
{
    if (t == T)
    {
        return 0;
    }
 
    if (w > W)
    {
        return 0;
    }
 
    if (D[t][w][now] >=0)
    {
        return D[t][w][now];
    }
 
    if (D[t][w][now] == -1)
    {
        D[t][w][now] = 0;
    }
    
 
    if (v[t] == now)
    {
        D[t][w][now] = max(go(t + 1, w + 1, 3 - now), go(t + 1, w, now)) + 1;
    }
    else
    {
        D[t][w][now] = max(go(t + 1, w + 1, 3 - now), go(t + 1, w, now));
    }
 
    
    return D[t][w][now];
}
int main()
{
    
    
    scanf("%d %d", &T, &W);
    v.resize(T);
    memset(D, -1, sizeof(D));
 
    for (int i = 0; i < T; i++)
    {
        scanf("%d", &v[i]);
    }
    
    printf("%d\n", max(go(0, 0, 1),go(0,1,2)));
 
    return 0;
}

<정답 코드>

#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
vector<int> v;
int D[1001][31][2];
int go(int t, int w, int now)
{
 
    if (w < 0)
    {
        return 0;
    }
 
 
    if (t == 0)
    {
        if (now == 1)
        {
            if (v[0] == now)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }
        else
        {
            if (w > 0)
            {
                if (v[0] == now)
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
            else
            {
                return 0;
            }
        }
    }
 
    
    if (D[t][w][now] >= 0)
    {
        return D[t][w][now];
    }
 
    if (D[t][w][now] == -1)
    {
        D[t][w][now] = 0;
    }
 
    if (v[t] == now)
    {
        D[t][w][now] = max(go(t - 1, w - 1, 3 - now), go(t - 1, w, now)) + 1;
    }
    else
    {
        D[t][w][now] = max(go(t - 1, w - 1, 3 - now), go(t - 1, w, now));
    }
 
    return D[t][w][now];
}
int main()
{
    int T, W;
 
    scanf("%d %d", &T, &W);
    v.resize(T);
    memset(D, -1, sizeof(D));
 
    for (int i = 0; i < T; i++)
    {
        scanf("%d", &v[i]);
    }
 
    printf("%d\n", max(go(T - 1, W, 1), go(T - 1, W, 2)));
 
    return 0;
}