Boj 2240 c++ 자두나무

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

 

 

문제

 

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 

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

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

 

 

 

 

접근 & 풀이

이 문제 또한 이전 상태가 이후 상태를 업데이트 할 때 반영되는 dp 문제이다. dp의 상태를 정의할 수 있는 요소는 시간 T, 자두의 현재 위치, 지금까지 움직인 횟수 W이다.

 

매 초마다 자두가 떨어지는 위치를 새로운 배열에 담아 dp 배열을 초기화한다.

 

자두는 처음에는 1번 나무에 있기에 첫번째 자두의 위치에 따라 dp 배열을 초기화 한다.

 

    if(ja[1] == 1)
        dp[1][0][1] = 1; // 자두는 1번에 있기에 움직일 필요가 없음
    else
        dp[1][1][2] = 1; // 첫번째 자두를 먹기 위해 1번 나무에서 2번 나무로 1번 움직임

 

이후에는 움직일 수 있는 최대 횟수 W 까지 모든 dp 배열을 초기화해주면 된다.

 

정답을 구할 때에는 모든 움직인 횟수 중에서 최댓값만을 취하면 된다.

 

    for(int i = 0; i <= W; i++) {
        ans = max(ans, dp[T][i][1]);
        ans = max(ans, dp[T][i][2]);
    }
    cout << ans;

 

 

정답코드

 

#include <iostream>

using namespace std;

int ja[1001], dp[1001][31][3];

int main() {

    int T, W, ans = 0;

    cin >> T >> W;

    for(int i = 1; i <= T; i++) {
        cin >> ja[i];
    }

    if(ja[1] == 1)
        dp[1][0][1] = 1;
    else
        dp[1][1][2] = 1;

    for(int i = 2; i <= T; i++) {

        if(ja[i] == 1)
            dp[i][0][1] = dp[i-1][0][1] + 1;

        for(int j = 1; j <= W; j++) {
            if(ja[i] == 1) {
                dp[i][j][1] = max(dp[i-1][j-1][2], dp[i-1][j][1]) + 1;
                dp[i][j][2] = max(dp[i-1][j-1][1], dp[i-1][j][2]);
            } else {
                dp[i][j][1] = max(dp[i-1][j-1][2], dp[i-1][j][1]);
                dp[i][j][2] = max(dp[i-1][j-1][1], dp[i-1][j][2]) + 1;
             }
        }
    }

    for(int i = 0; i <= W; i++) {
        ans = max(ans, dp[T][i][1]);
        ans = max(ans, dp[T][i][2]);
    }
    cout << ans;
}