[Algorithm]Baekjoon 2240번 :: 자두나무

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

2240번: 자두나무

 
int t, w;
int treeNums[1001] = { 0 };
int dp[2][1001][31] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t >> w;
 
    for (int i = 1; i <= t; ++i)
    {
        cin >> treeNums[i];
        dp[0][i][0] = dp[0][i - 1][0] + (treeNums[i] == 1);
    }
 
    for (int i = 1; i <= w; ++i) // 이동횟수
    {
        for (int j = 1; j <= t; ++j) // 자두 떨어지는 턴.
        {
            dp[0][j][i] = max(dp[0][j - 1][i] + (treeNums[j] == 1), dp[1][j - 1][i - 1] + (treeNums[j] == 1));
            dp[1][j][i] = max(dp[1][j - 1][i] + (treeNums[j] == 2), dp[0][j - 1][i - 1] + (treeNums[j] == 2));
        }
    }
 
    int result = 0;
 
    for (int i = 0; i < 2; ++i)
    {
        for (int j = 0; j <= w; ++j)
        {
            result = max(result, dp[i][t][j]);
        }
    }
 
    cout << result;
}
 
 
 

 

두 나무사이를 최대 w번 왔다갔다하면서 t번에 걸친 자두를 최대 몇개까지 얻을 수 있는지 구하는 문제이다.

최대 w번이라는것은, 아예 안움직여도 상관없다는 것이다. 그리고 그게 더 이득인 경우가 존재하는것도 당연하다.

 

주어지는 경우의 수가 3가지이니, dp테이블을 3차원으로 잡아본다.

나무개수는 최대 2개, t값은 최대 1000, 이동횟수는 최대 30이니 dp[2][1001][31]로 잡는다.

 

이 경우, dp[0][i][j]는 첫번째 나무에서, i번째일 때, 그리고 이동횟수가 j번남았을 때 얻을 수 있는 자두의 최대개수이다.

즉 dp[0][5][3] = 10 이라면, 첫번째나무에서 5번째 자두를 반영했을 때, 그리고 이동횟수가 3번남았을 때 얻을 수 있는 자두의 최대개수가 10개라는 것이다. (이후 설명은 첫번째나무로만 기준)

 

그러면 어떻게 dp테이블을 업데이트 해야할까? 

기본적으로 이전차례(i-1번째 차례)에서 뭔가 값을 가져와야 하긴 한다. 

이 때, 첫번째나무라고 첫번째나무에서만 값을 가져오는게 아니라 두번째나무에서도 비교할 값을 가져올 수 있다.

다만, 반대편의 나무에서 값을 가져오려면 이동을 해야하기 때문에 이동횟수를 한번 차감해야한다.

그렇기 때문에 반대편나무에서 값을 가져올 때 dp[0][i-1][j-1] 값을 가져오는 것이다.

 

그리고 이 dp테이블업데이트 로직을 수행하기 전에, 반드시 dp[0][i][0]에 대해 값을 업데이트 해줘야한다. (코드17라인)

왜냐하면, 이동자체를 아예 안할수도 있기 때문이다. 이동자체를 안했을 때, 시작위치가 1번나무이기 때문에 1번나무에서 떨어지는 자두만 업데이트 해주면 된다. 

이동을 안하고 그냥 1번에서 받아먹기만하는게 제일 큰값이 나올 수 있기 때문에, 반드시 수행해줘야 한다.

 

 

위의 풀이는 바텀업이고, 탑다운방식으로도 한번 코드를 작성해보고 싶었다.

확실히 자신이 이 문제에 대해 이해를 했다면, 코드로 반드시 표현할 수 있어야 하기 때문이다.

 

 
 
int t, w;
int treeNums[1001] = { 0 };
int dp[2][1001][31] = { 0 };
 
int dfs(int curTree, int time, int moveCount) // 0,1,0  으로 시작.
{
    if (time == t+1) return 0;
 
    if (dp[curTree][time][moveCount] != -1)
    {
        return dp[curTree][time][moveCount];
    }
 
    int result = 0;
 
    if (curTree == 0) // 현재 첫번째나무면
    {
        result = dfs(0, time + 1, moveCount) + (treeNums[time] == 1);
        if (moveCount < w)
        {
            result = max(result, dfs(1, time + 1, moveCount + 1) + (treeNums[time] == 1));
        }
    }
    else // 두번째 나무면
    {
        result = dfs(1, time + 1, moveCount) + (treeNums[time] == 2);
        if (moveCount < w)
        {
            result = max(result, dfs(0, time + 1, moveCount + 1) + (treeNums[time] == 2));
        }
    }
 
    return dp[curTree][time][moveCount] = result;
}
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t >> w;
 
    for (int i = 1; i <= t; ++i)
    {
        cin >> treeNums[i];
    }
 
    memset(dp, -1, sizeof(dp));
    cout << max(dfs(0, 1, 0), dfs(1, 1, 1));
}
 
 
 

 

다만, 비슷한문제를 좀 더 많이 풀어봐야 할 것 같다. 아직은 자신이 없다.