[👊DP뿌시기 #5] (BOJ 2240) 자두나무

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

2240번: 자두나무

 

 

문제

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

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

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

입력

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

출력

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

 

---

접근법

이번에는 시간, 이동횟수, 현재위치 이렇게 3개의 변수가 필요하다.

처음에 클래스를 이용해 풀이하려고 했지만, 더 복잡해서 3차원 배열을 이동하였다.

 

DP[time][cnt][pos] : [시간][이동횟수][현재위치]

 

우리가 N번째 시간일 때, 우리는 두 가지 경우를 생각해볼 수 있다.

 

1. 가만히 있는 경우 2. 움직이는 경우

 

자두개수는 별개로 나누어서 생각해도 된다.

왜냐하면 점수가 맞으면 +1을 하면 되기 때문

 

DP[4][1][2] 일 때, 위 두가지 경우는 각각 다음과 같이 표현된다.

 

1. 가만히 있는 경우 = DP[4-1][1][2]

2. 움직이는 경우 = DP[4-1][1-1][1]

 

위 두 가지 경우 중 가장 큰 값을 저장하면 된다.

 

따라서, DP[4][1][2] = max(DP[4-1][1][2], DP[4-1][1-1][1])

여기다 자두가 2번 (arr[4] == 2) 이면 +1을 해주면된다.

DP[4][1][2] = max(DP[4-1][1][2] +  (arr[4] == 2) , DP[4-1][1-1][1] +  (arr[4] == 2) )

 

마찬가지로 DP[4][1][1] = max(DP[4-1][1][1] +  (arr[4] == 2) , DP[4-1][1-1][2] +  (arr[4] == 2) )

 

근데 여기서 문제가 있다.

 

5 1
2
2
1
1
1

 

위 테스트를 입력하면 3이 아닌 4가 나온다.

왜 일까?

 

그 이유는 이동횟수가 0번인데, 2번 위치에 있는 경우도 포함되기 때문

 

시작이 1번 위치이기 때문에 2번 위치로 가려면 무조건 이동횟수를 1회 사용해야한다.

그래서 위 조건을 지키지 않으면 T=1일때, DP[1][0][2]가 1이 나와서 꼬인다.

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

#define MAX 31

// [time][cnt][pos]
int dp[1001][31][3];
int arr[1001];

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

    int t, w, tmp;
    int res = 0;
    cin >> t >> w;

    // 자두 떨어지는 위치 받기
    for (int i = 1; i <= t; i++) {
        cin >> arr[i];
    }

    for (int cnt = 0; cnt <= w; cnt++) {
        for (int time = 1; time <= t; time++) {

            dp[time][cnt][1] = max(dp[time - 1][cnt][1] + (arr[time] == 1),
                dp[time - 1][cnt - 1][2] + (arr[time] == 1));

            // 이동을 했을 때만, 2번 위치에 대한 DP를 구한다!
            if (cnt != 0) {
                dp[time][cnt][2] = max(dp[time - 1][cnt - 1][1] + (arr[time] == 2),
                    dp[time - 1][cnt][2] + (arr[time] == 2));
            }

        }
    }

    for (int pos = 1; pos <= 2; pos++) {
        for (int cnt = 0; cnt <= w; cnt++) {
            res = max(dp[t][cnt][pos], res);
        }
    }

    cout << res << endl;
    return 0;
}

반례 찾는데 많은 시간을 사용함...

 

틀린 점이나 보충설명 언제나 환영합니다!

저도 배우는 입장이라 틀릴 수 있어요ㅜㅜ