BOJ 2240 자두나무

 

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

2240번: 자두나무

 

1. dp 의 정의

dp[t][p][r] : t 시간에, p 번 나무 아래에서 움직일 수 있는 횟수가 r 번 남아 있을 때의 최댓값.

 

단,  p 는 0, 1 값을 가지고 이는 1 , 2 번 나무를 뜻한다.

주인공 자두는 1 번 나무 아래에서 시작한다는 조건이 있는데 0 초에  0(1 번나무)에서 시작하는 것으로 설계하면 된다.

 

2. Transition 

나무 위치 p 와 t 번째 입력(시간 t 에서 자두가 떨어지는 나무) 같으면 1 을 더하고 아니면 0이 더해진다.

 

(1) 만약 현재의 위치를 t+1 시간까지 고수했을 때 얻을 수 있는 값은 

$$ dp[t+1][p][r] + (arr[t]-1==p)$$

이다. ( 편의상 입력값은 1, 2을 그대로 받았고 나무 번호는 1, 2 를 0, 1 로 바꾸었기에 arr[t]-1 과 p 를 비교했다. )

 

(2) 위치를 변경하면 p 에서 1-p 나무로 위치를 옮기게 되고 움직일 수 있는 횟수는 1 줄어든 r-1 이 된다. 따라서

$$ dp[t+1][1-p][r-1] + (arr[t]-1==p)$$

을 얻는다.

 

#include<bits/stdc++.h>

using namespace std;

int T, W;
int arr[1001],dp[1001][2][31];

int recur(int t,int p,int r){
    if(t>T) return 0;
    int &ret=dp[t][p][r];
    if(ret!=-1) return ret;
    
    ret=0;
    ret=max(ret,recur(t+1,p,r)+(arr[t]-1==p));
    if(r)
        ret=max(ret,recur(t+1,1-p,r-1)+(arr[t]-1==1-p));
    
    return ret;
}

int main(){
    memset(dp,-1,sizeof dp);
    scanf("%d%d",&T,&W);
    for(int i=1;i<=T;i++)
        scanf("%d",&arr[i]);
    printf("%d\n",recur(0,0,W));
}