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

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

문제

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

입력

첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.

출력

첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.

---

풀이

자두가 몇 번째 자두를 받고 있는지(t), 몇 번 이동했는지(w), 어떤 나무에 서있는지(1 or 2)를 dp로 푸는 문제이다.

문제에서의 예제를 dp 테이블로 보면 다음과 같다.

 

가로는 몇 번째 자두를 받고 있는지와 어떤 나무에 서있는지를, 세로는 몇 번 이동했는지를 나타내며

편의를 위해 세로(w)를 0~2가 아닌 1~3으로 설정하였다. (w가 0일 때를 모두 0으로 채우기 위해)

먼저 세로가 1일 때를 채우면 다음과 같다.

 

 

세로가 1일 때는 자두가 이동을 하지 않는 경우이므로 자두는 1번 나무에 계속 서 있을 것이다.

따라서 2번 나무에 위치한 경우는 모두 0일 것이고 1번 나무에 위치한 경우만 생각하면 된다.

1번 나무에 자두가 떨어지는 경우는 2, 3, 6, 7번째이므로 가로가 2, 3, 6, 7일 때 값이 1씩 증가한다.

 

 

이어서 세로가 2일 때를 채워나가보자. 세로가 2일 때는 자두가 1번 이동을 하는 경우이다.

맨 처음에 자두가 이동을 한다면 2번 나무에서 떨어지는 자두를 받을 수 있을 것이므로 0 / 1이 채워진다.

 

 

다음으로 2번째 자두가 떨어지고 자두가 1번 나무에 서 있을 때를 생각해보자. 자두가 1번 나무에 서 있는 경우는 

1. 자두가 이전 자두가 떨어질 때부터 1번 나무에 서있었고 이동을 하지 않았을 때

2. 자두가 이전 자두가 떨어질 때 2번 나무에 서있었고 현재 이동하였을 때 2가지의 경우가 존재한다.

따라서 2가지 값 중에 더 큰 값을 찾아 저장해주면 된다.

여기서 주의할 점은 실제로 2번째 자두가 1번 나무에 떨어졌으므로 둘 중 큰 값에 +1을 해주어야 하는 것이다.

 

 

2번째 자두가 떨어지고 자두가 2번 나무에 서 있을 때도 마찬가지로 두 가지 경우 중 큰 값인 1을 저장하면 된다.

다만 이 경우에는 2번 나무에 자두가 떨어지지 않으므로 값을 그대로 가져가면 된다.

 

이를 바탕으로 dp테이블을 모두 채우면 다음과 같다.

 

정답으로는 마지막 (7, 3, 1)과 (7, 3, 2) 중의 최댓값을 출력해주면 된다.

 

코드

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

bool plums[1001];
int dp[1001][32][3];

int main(){
    int t, w;
    cin >> t >> w;

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

    // dp[i][j][k] 는 i번째 자두가 떨어질 때 j-1번 이동했고 자두가 k번 나무에 있을 때 최대 자두 수
    for (int i = 1; i <= t; i++){
        for (int j = 1; j <= w+1; j++){
            // 1번 나무에 위치한 경우
            dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][2]);
            // 2번 나무에 위치한 경우
            dp[i][j][2] = max(dp[i-1][j][2], dp[i-1][j-1][1]);

            // 자두가 떨어지는 나무에 +1
            if (!plums[i]){
                dp[i][j][1]++;
            }
            else{
                // 맨 처음에 j=1일 때 2번 나무에 자두가 떨어진다면 카운트 X
                if (j == 1){
                    continue;
                }
                dp[i][j][2]++;
            }
        }
    }

    cout << max(dp[t][w+1][1], dp[t][w+1][2]);
}