[BAEKJOON] 2240 자두나무 (C++)

문제 링크

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

 

문제

자두나무가 두그루 존재한다. 

1초에 한 개씩 T초동안 둘 중 하나의 자두나무에서 자두가 떨어진다.

자두나무의 아래에 서있으면 자두를 얻을 수 있다.

W만큼 서있는 위치를 변경할 수 있다.

얻을 수 있는 자두의 최대개수를 구한다.

 

풀이

다이나믹 프로그래밍 문제이다.

다이나믹 프로그래밍을 풀기 위해서는 먼저 테이블을 정의해야한다.

 

T초후에 얻을 수 있는 자두의 최대개수이므로 각 초마다 얻을 수 있는 자두의 최대개수를 알아한다.

따라서 베이스를 DP[T] 로 잡는다.

하지만 1차원 배열로는 각 초에서 몇번이나 위치를 변경했는지 알 수 없다. 또 현재 위치가 어떤 자두나무 아래인지에 대한 정보도 필요할 것 같다.

 

이 문제에서는 자두나무가 2그루밖에 존재하지 않는다. 

즉, 현재 위치를 변경한 횟수를 안다면 현재 위치를 알 수 있다. (시작은 1번 나무이기 때문)

 

따라서 테이블을 DP[T][W]로 잡는다. DP[i][j]의 값이 의미하는 바는 i초에서 j번 위치를 변경했을 때 얻을 수 있는 자두의 최대값이다.

 

각 초에서 각 변경횟수에 따른 최대 자두 획득 가능 개수를 구한다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>

#define endl "\n"

using namespace std;

int T, W;
int DP[1010][33];
void Solve() {
    cin >> T >> W;

    int tree, now, ans = 0;
    for (int i = 1; i <= T; i++) {
        cin >> tree;
        for (int j = 0; j <= W; j++) {
            now = j % 2 + 1;
            if (now == tree) DP[i][j] = DP[i - 1][j] + 1;
            else if(j > 0) DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - 1] + 1);

            ans = max(ans, DP[i][j]);
        }
    }
    cout << ans;

}


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

    return 0;
}