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

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

 

최댓값을 구하는 문제로 가장 먼저 그리디, 완전탐색, DP가 떠오르는 것이 일반적이다.

어떻게 풀 수 있을까? 먼저 최대 자두가 떨어지는 숫자는 1000이고 움직일 수 있는 횟수는 30이다.

 

1. Greedy

탐욕법으로 풀 수 있을까? 탐욕법이 성립하기 위해서는 지금 선택하는 조건이 이후의 선택에 영향을 주어선 안된다.

즉, 2번에서 자두가 떨어질 때 이동하여 잡는 이 선택이 뒤에서 영향을 주어선 안되는데 조금만 생각해도 당연히 영향을 줄 수 밖에 없는 구조이다. 그러므로 탐욕법으로는 풀 수 없다.

2. 완전탐색

완전탐색으로는 정확도만 풀이가 가능하다. 한 지점에서 취할 수 있는 경우의 수는 두가지다. 이동하거나, 가만있거나 

그러므로 2^30의 시간이 소요되고 이는 1,073,741,824 10억이 넘기 때문에 시간초과가 난다. 

완전탐색도 탈락이다. 

3. 동적계획법

남은 것은 동적계획법이다. 완전탐색과 그리디를 살펴보았을 때 알게된 것이 있다.

1. 현재의 행동은 이후에 영향을 미칠 수 있으므로 계속 저장해두어야한다.

2. 자두가 떨어질 때 취할 수 있는 행동은 가만이 서있기 or 이동하기 두개이다.

 

아하.. 그렇다면 DP(나무아래위치, 시간, 지금까지 이동한 횟수) = 이번 시간에 나무 아래 위치(1or2)에서 이동한 횟수 중 가장 큰 자두의 수이면 되지 않을까?

 

그리고 메모이제이션을 통해 이전의 자두 상태에서 각 최적의 수를 갱신해가면 될 것 같다.

이번 시간에서 모든 이동 횟수를 살펴본다고 하면 걸리는 시간은 1000 * 30 으로 매우 짧은 시간에 처리할 수 있겠다.

 

점화식을 새워보자

 

DP[Position][Time][MoveCnt] 

 

만약 1번위치에 자두가 떨어진다면, 이전 시간의 2번 위치에 있다가 이동하여 쟁취할수도 있고 원래 1번에 있었다면 그대로 받아먹으면 된다. 그러므로

 

DP[1][Time][MoveCnt] = MAX (DP[1][Time - 1][MoveCnt] , DP[2][Time - 1][MoveCnt - 1]) + 1

 

으로 정의할 수 있을 것이다. 그리고 1번위치에 자두가 떨어진다고 해서 꼭 2번에 있던 경우에서 이동할 필요는 없으므로 Position이 2인 경우도 정의해준다.

 

DP[2][Time][MoveCnt] = MAX (DP[1][Time - 1][MoveCnt - 1] , DP[2][Time - 1][MoveCnt])

 

1에서 2로 이동했더나 2에서 가만있던 경우다.

 

정리하면 

 

if 1번에 떨어지면
dp[1][i][j] = max(dp[1][i - 1][j], dp[2][i - 1][j - 1]) + 1;
dp[2][i][j] = max(dp[1][i - 1][j - 1], dp[2][i - 1][j]);

if 2번에 떨어지면
dp[1][i][j] = max(dp[1][i - 1][j], dp[2][i - 1][j - 1]);
dp[2][i][j] = max(dp[1][i - 1][j - 1], dp[2][i - 1][j]) + 1;

 

이렇게 정의할 수 있고 초기값은 

 

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

 

이렇게 될 것이다. 1번에 처음 온다면 0번 움직일 때 1일 것이고 2번에 온다면 한번움직여서 1을 만들 수도 있다.

 

이 때 시간1일 때는 진행했으니까 2부터 진행시키고, 각 시간대의 move횟수를 메모이제이션으로 갱신하는 방식으로 위 점화식을 활용한다.

 

#include <iostream>

using namespace std;

int dp[3][1001][32]; // 위치, 시간, 이동횟수
int value[1001];

int main(){
    int N, M; cin >> N >> M;
    for(int i = 0; i < N; i++) cin >> value[i];

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

    int answer = 1;

    for(int i = 2; i <= N; i++){
        for(int j = 0; j <= M; j++){
            if(value[i - 1] == 1){
                if(j == 0) {
                    dp[1][i][j] = dp[1][i - 1][j] + 1;
                    dp[2][i][j] = dp[2][i - 1][j];
                }else{
                    dp[1][i][j] = max(dp[1][i - 1][j], dp[2][i - 1][j - 1]) + 1;
                    dp[2][i][j] = max(dp[1][i - 1][j - 1], dp[2][i - 1][j]);
                }
            }else{
                if(j == 0) {
                    dp[1][i][j] = dp[1][i - 1][j];
                    dp[2][i][j] = dp[2][i - 1][j] + 1;
                }else{
                    dp[1][i][j] = max(dp[1][i - 1][j], dp[2][i - 1][j - 1]);
                    dp[2][i][j] = max(dp[1][i - 1][j - 1], dp[2][i - 1][j]) + 1; 
                }
            }
            cout << endl;
            printf("dp[1][%d][%d] = %d", i, j, dp[1][i][j]);
            cout << endl;
            printf("dp[2][%d][%d] = %d", i, j, dp[2][i][j]);
            cout << endl;

            answer = max(answer, max(dp[1][i][j], dp[2][i][j]));
        }
    }

    cout << answer;
}

 

 

다이나믹프로그래밍은 정말 어렵다.

 

점화식을 도출하는 것 부터 DP변수를 어떻게 정의할지 조차 쉽지 않다. 이게 골드 5라니..