백준 2240 - 자두나무(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2240

2240번: 자두나무

자두나무에서 자두가 1초 간격으로 떨어집니다. 2개의 자두나무 중 한 곳에서만 떨어질 때,

W이하로 움직이면서 받을 수 있는 자두의 개수를 구하는 문제입니다. (시작점은 1번 자두나무입니다.)

 

예제 입력의 경우에는

2~3초 동안은 1번 -> 2번 자두나무로 이동 -> 4~5초동안 2번 -> 1번 자두나무로 이동 -> 6~7초동안 1번

이와 같이 움직여 7개를 먹습니다.

 

이 문제를 풀기 위해서는 X초에서 0~W번 움직여서 먹을 수 있는 최대 자두의 개수를 저장하는 것이 중요합니다.

0~W를 전부 저장해줘야하는 이유는 예제 입력에서 찾을 수 있는데,

1초 -> 2번 자두 (0, 1, 0)

2초 -> 1번 자두 (1, 1, 2)

3초 -> 1번 자두 (2, 1, 3)

4초 -> 2번 자두 (2, 3, 3)

5초 -> 2번 자두 (2, 4, 3)

6초 -> 1번 자두 (3, 4, 5)

7초 -> 1번 자두 (4, 4, 6) -> 이 중, 6이 가장 큼으로 6이 정답이 된다.

-> 만약, 0~W를 전부 저장하지 않았다면, 1초에 2번 자두로 넘어가는 순간, 다른 값이 나올 것입니다.

 

위의 방법을 살펴보면 알 수 있는 것이 있습니다.

1. 짝수번 이동했다면 무조건 1번 나무에 있다.

2. 홀수번 이동했다면 무조건 2번 나무에 있다.

 

또한, X초에서 몇번 자두가 내려오는지도 중요합니다.

1. 내가 홀수번 이동했을 때, 1번 자두가 내려오는 중이라면 현재 위치에서는 못먹는다.(움직이면 먹는다.)

2. 내가 짝수번 이동했을 때, 2번 자두가 내려오는 중이라면 현재 위치에서는 못먹는다.(움직이면 먹는다.)

 

 

따라서 이를 정리하면 ([T][W]를 [초][이동한 횟수] 라고 가정) 

1. [X][Y]에서 현재 내려오는 자두가 1번 자두일 때

   1-1. 현재 짝수번 이동했다면 [X-1][Y]+1 와 [X-1][Y-1]+1 의 값 중, 큰 값을 가져온다.

   1-2. 현재 홀수번 이동했다면 [X-1][Y]의 값으로 저장한다.

2. [X][Y]에서 현재 내려오는 자두가 2번 자두일 때

   2-1. 현재 홀수번 이동했다면 [X-1][Y]+1 와 [X-1][Y-1]+1 의 값 중, 큰 값을 가져온다.

   2-2. 현재 짝수번 이동했다면 [X-1][Y]의 값으로 저장한다.

 

 

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#define INF 987654321

using namespace std;

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

void solve(){
    for(int i = 1; i <= T; i++){
        if(down[i] == 1){
            for(int j = 0; j <= W; j++){
                if(j%2 == 0){
                    dp[i][j] = dp[i-1][j] + 1;
                    if(j > 0) dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
                }
                else{
                    dp[i][j] = dp[i-1][j];
                }
            }   
        }
        else{
            for(int j = 0; j <= W; j++){
                if(j%2 == 0) {
                    dp[i][j] = dp[i-1][j];
                }
                else{
                    dp[i][j] = max(dp[i-1][j] + 1, dp[i-1][j-1] + 1);
                }
            }    
        }
    }
    for(int i = 0; i <= W; i++){
        maxi = max(maxi, dp[T][i]);
    }
    cout << maxi;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> T >> W;
    for(int i = 1; i <= T; i++) cin >> down[i];
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.