2240. 자두나무

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

2240번: 자두나무

 

풀이

필요 알고리즘: 다이나믹 프로그래밍(DP)

 

자두를 받고자 움직이는 경우의 수를 모두 검사하기엔 너무 많고, 하나하나 체크하기도 난해하다. 게다가 최대로 받는 자두의 개수를 구하라고 했으므로, DP로 각 시간마다 최대로 받는 자두 개수를 저장한다면 실행 속도를 획기적으로 줄일 수 있다.

 

최대로 받는 자두 개수를 저장할 2차원 배열 dp를 선언하자. dp[i][j]는 i초째에서 j번 움직였을 때 최대로 받는 자두 개수로 정의한다. 0초째에는 자두가 떨어지지 않으므로 당연히 dp[0][0] ~ dp[0][j]의 값은 0일 것이다.

 

다음으로 점화식을 생각해 보자. dp[i][j]는 i초째에서 j번 움직였을 때 최대로 받는 자두 개수이다. 즉, i - 1초까지 j - 1번 움직이고 1번 움직인 결과인지, j번 움직이고 가만히 있는 결과인지 둘 중 하나이다. 그리고 우리는 배열 dp에 최댓값을 담기로 정의했으므로 점화식은 dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + (i초에서 자두를 받았는지 여부)이다.

 

위 점화식에서 (i초에서 자두를 받았는지 여부)는 의외로 간단하게 쓸 수 있는데, 자두가 두 그루의 나무에서만 떨어지고, 떨어지는 위치가 1, 2로 주어짐을 이용하면 된다. 일단 맨 처음 1번 나무에 서 있으므로, 짝수만큼(0, 2, 4, ...번) 움직이면 반드시 1번 나무의 자두만, 홀수만큼(1, 3, 5, ...번) 움직이면 2번 나무의 자두만 받을 수 있음을 알 수 있다. 이를 종합적으로 고려하면 자두를 받았는지 여부는 (plum + j) % 2로 표현 가능하다. 이 식은 j번 움직였을 때 자두를 받았으면 1, 못 받았으면 0을 출력한다.

 

시간 복잡도

\(T\)초 동안 움직인 횟수 각각, 즉 \(W + 1\)가지 경우마다 받을 수 있는 자두의 개수를 확인하므로 시간 복잡도는 \(O(TW)\)이다.

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int T, W;
int dp[1001][31];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> T >> W;
    
    int plum;
    for(int i = 1; i <= T; i++) {
        cin >> plum;
        
        dp[i][0] = dp[i - 1][0] + plum % 2;
        for(int j = 1; j <= min(i, W); j++) {
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + (j + plum) % 2;
        }
    }
    
    cout << *max_element(dp[T], dp[T] + W + 1);
    return 0;
}

중첩 반복문에서 j <= min(i, W)로 반복 범위를 걸어둔 것을 볼 수 있는데, 이는 i초일 때 i + 1번 이상 움직였을 때 경우를 계산하게 되는 사태를 막기 위해서이다. 아직 2초째인데 5번 움직일 수는 없지 않겠는가?