[2240번] 자두 나무

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

3차원 배열을 이용한 점화식이 필요한 문제이다.

하나씩 보며 이야기 해보자.

jadu[i][pos] :: i초에 자두가 pos위치에 있다면 1로 설정해준다.

예제입력에서는 2로 먼저 입력되기에 jadu[1][2] = 1이 된다.

// 1초에 1번 위치이고 0번 움직일 때

// 1초에 2번 위치이고 1번 움직일 때 

// 자두가 있는곳은 자두를 먹는다.

DP[1][1][0] = jadu[1][1];

DP[1][2][1] = jadu[1][2];

이 과정은 DP값 초기화 과정이고,

1초에 1번 위치에 사람이 있고 0번 움직였을 때, 자두가 1초에 어디있었냐에 따라 0,1을 받는다.

1초에 2번 위치에 사람이 있고 1번 움직였을 때, 자두가 1초에 어디있었냐에 따라 0,1을 받는다.

(처음에 사람은 1번위치에 있었으니 2번 위치로 가기 위해서는 1번 움직여야한다.)

// i초에 1번 위치에 이동횟수 k로 있을때 DP는

// i-1초에 1번위치에 그대로 가만히 있을 때 또는 2번위치에서 한칸 움직였을때의 최대

DP[i][1][k] = max(DP[i - 1][1][k], DP[i - 1][2][k - 1]) + jadu[i][1];

DP[i][2][k] = max(DP[i - 1][2][k], DP[i - 1][1][k - 1]) + jadu[i][2];

i초에 1번위치에서 k번 움직였을 때, i-1초에 1번위치에 가만히 있는 것 또는 2번->1번 위치로 왔을 때 중 최대를 의미한다.

i초에 2번위치에서 k번 움직였을 때, i-1초에 2번위치에 가만히 있는 것 또는 1번->2번 위치로 왔을 때 중 최대를 의미한다.

ans = max(ans, DP[i][1][k]);

ans = max(ans, DP[i][2][k]);

이제 자두를 가장 많이 먹은 상황을 ans에 담으면서 계속 간다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
// 초, 위치, 이동수 = 먹은 자두
int DP[1003][3][33];
// 초, 위치 = 자두 있으면 1 없으면 0
int jadu[1003][3];
 
int main()
{
    int T, W;
    scanf("%d %d", &T, &W);
 
    for (int i = 1; i <= T; i++)
    {
        int pos;
        scanf("%d", &pos);
 
        jadu[i][pos] = 1;
    }
 
    // 1초에 1번 위치이고 0번 움직일 때
    // 1초에 2번 위치이고 1번 움직일 때 
    // 자두가 있는곳은 자두를 먹는다.
    DP[1][1][0] = jadu[1][1];
    DP[1][2][1] = jadu[1][2];
 
    // T초동안 DP
    int ans = 0;
    for (int i = 2; i <= T; i++)
    {
        for (int k = 0; k <= W; k++)
        {            
            // i초에 1번 위치에 이동횟수 k로 있을때 DP는
            // i-1초에 1번위치에 그대로 가만히 있을 때 또는 2번위치에서 한칸 움직였을때의 최대
            DP[i][1][k] = max(DP[i - 1][1][k], DP[i - 1][2][k - 1]) + jadu[i][1];
            DP[i][2][k] = max(DP[i - 1][2][k], DP[i - 1][1][k - 1]) + jadu[i][2];
 
            ans = max(ans, DP[i][1][k]);
            ans = max(ans, DP[i][2][k]);
        }
    }
    
    printf("%d", ans);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>