백준 [C++] 2240 자두나무

<조건 분석>

 

1. 30번 이동 가능. 나무는 1번 나무, 2번 나무 존재. 그러면 경우의수가 최대 2^30임. (1번 나무 혹은 2번 나무를 30번 이동 가능하니까).

 

2. 그럼 무식한 완전탐색으로는 불가능. 지나왔던 길을 저장하는 방법을 택해서 복잡도를 줄여봐야 함.

 

<문제 해결 포인트>

 

1. 현재 위치에서 받을 수 있는 자두 경우의 수, 다음 위치에서 받을 수 있는 자두 경우의 수를 재귀 때 더해주는 것이 포인트임.

 

2. DP는 재귀 때 경우의 수를 더해주면서, 재귀 탈출 루프에서는 0의 경우의 수를 던지는 게 포인트 인 것 같음.

 

 

#include <bits/stdc++.h>
using namespace std;

int t, w;
int tree[1004];
int dp[3][31][1004]; // 현재 위치 , 남은 이동 횟수, Time

int go(int cur, int movecnt, int time)
{
    if (time > t) return 0; // 시간을 넘어가면 다 0의 경우의 수

    int plum = (tree[time] == cur) ? 1 : 0;

    int& ret = dp[cur][movecnt][time];
    if (ret != -1) return ret;

    ret = max(ret, go(cur, movecnt, time + 1) + plum);

    if (movecnt > 0) 
    {
        int npos = (cur == 1) ? 2 : 1;
        int nplum = (tree[time] == npos) ? 1 : 0;
        ret = max(ret, go(npos, movecnt - 1, time + 1) + nplum);
    }


    return ret;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> t >> w;

    memset(dp, -1, sizeof(dp));

    for (int i = 1; i <= t; i++)
    {
        cin >> tree[i];
    }

    cout << go(1, w, 1);

    return 0;
}

 

 

DP는 감 잡을 듯 하면서도 잡히지 않음...