[BOJ 2240] 자두나무

2240번: 자두나무

 

1. 문제

 

2. 구현 아이디어

자두는 최대 30번 움직이고, 1번 나무 또는 2번 나무로 이동하므로(0, 1) 전체 경우의 수는 2^30가지이다.

그렇기 때문에 완전탐색으로 푸는 것은 불가능하다.

 

(i-1)초일 때 최대 자두 갯수를 알면, 이동할지 말지 여부에 따라 i초일 때의 최대 자두 갯수를 알 수 있기 때문에 DP로 문제를 풀 수 있다.

 

문제에서 3가지 상태(이동 횟수, 자두의 위치, 흐른 시간)이 있기 때문에 3차원 배열로 각 상태에 따른 자두의 최대 개수를 DP 배열로 관리해야 한다.

 

🍑 현재 위치에서의 자두의 최대 갯수 점화식 - f(x,y,z) 꼴
현재 위치가 1번 나무: jadu(w, 1, t) = ( jadu(w, 1, t-1) + jadu(w-1, 2, t-1) ) + (현재 위치가 1번 나무인지)
현재 위치가 2번 나무: jadu(w, 2, t) = ( jadu(w, 2, t-1) + jadu(w-1, 1, t-1) ) + (현재 위치가 2번 나무인지)

 

3. 전체 코드 1 - 틀렸습니다 

#include <bits/stdc++.h>

using namespace std;

int t, w; // T초 동안 최대 W번 움직임
int v[1001];
int dp[31][2][1001];
// dp[이동 횟수][자두의 위치][흐른 시간]
// 참고) 1번 나무의 인덱스는 0, 2번 나무의 인덱스는 1

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> t >> w;

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

    for (int i = 0; i <= w; ++i) { // 움직인 횟수
        for (int j = 1; j <= t; ++j) { // 초
            // 아예 안 움직였을 때는 항상 1번 나무 아래에 위치
            if (i == 0) {
                dp[i][0][j] = dp[i][0][j-1] + (v[j] == 1);
            }
            else {
                // 현재 위치까지 받은 누적 자두 = max(안 움직였을 때, 움직였을 때) + (현재 위치에서 받은 자두)
                
                // 1번 나무
                dp[i][0][j] = max(dp[i][0][j-1], dp[i-1][1][j-1]) + (v[j] == 1);
                // 2번 나무
                dp[i][1][j] = max(dp[i][1][j-1], dp[i-1][0][j-1]) + (v[j] == 2);
            }
        }
    }

    int ret = 0;
    for (int i = 0; i < 2; ++i) { // 자두 나무 번호
        for (int j = 0; j <= w; ++j) { // 움직인 횟수
            ret = max(ret, dp[j][i][t]);
        }
    }
    cout << ret << "\n";

    return 0;
}

 

마지막에 최종적인 자두의 최대 갯수를 구할 때 처음에는 '바로 dp[w][1][t]와 dp[w][2][t] 를 비교하면 되지 않을까?'라고 생각했다.

하지만, w번보다 적게 움직였을 때가 최대일 수 있기 때문에 반복문을 돌며 최대값을 구해야 한다.

4. 전체 코드 2 - 맞았습니다 !!

앞에서 자두가 떨어지는 나무의 번호를 입력받을 때 0부터 t-1까지로 입력을 받았다.

이렇게 될 경우 아래 반복문으로 DP를 돌 때, 인덱스가 맞지 않기 때문에 1부터 t까지 받도록 해야 한다.

입력을 받는 부분을 수정하여 문제를 최종적으로 해결할 수 있었다.

int main() {
    // 중략 ...
    
    // 자두가 떨어지는 나무의 번호를 입력받을 때 1부터 t까지 받는다
    for (int i = 1; i <= t; ++i) {
        cin >> v[i];
    }

    // 중략 ...
}