[백준 2240] 자두나무 C++

2240번: 자두나무

다이나믹 프로그래밍

---

 

1. 문제해결 아이디어

cnt초가 지났고, s번 움직였고, 사람 자두가 loc에 있을 때의 최댓값을 메모이제이션 해주었다.

 

사람의 위치가 그대로 라면 cnt가 T가 되기 전까지 진행이 가능하다.

사람의 위치를 바꾼다면 s가 W가 되기 전까지 위치를 바꿀 수 있다.

 

현재 위치에 따라서 자두를 먹는지, 못 먹는지를 판단해서 결과에 1을 더할지 말지를 결정한다.

---

2. 코드

top-down 방식으로 구현

#include <iostream>
#include <cstring>
using namespace std;
 
int T, W;
int jadu[1001], dp[1001][31][2];    // [시간][움직인 횟수][사람 자두의 위치]
 
int solve(int cnt, int s, int loc){
    if(cnt >= T) return 0;
    
    int &ret = dp[cnt][s][loc];
    if(ret != -1) return ret;
    
    int a = solve(cnt+1, s, loc);
    int b = 0;
    if(jadu[cnt] == loc) a += 1;
    
    if(s < W){
        b = solve(cnt+1, s+1, 1 - loc);
        if(jadu[cnt] == 1 - loc) b += 1;
    }
    
    ret = max(ret, max(a, b));
    
    return ret;
}
 
int main(){
    cin >> T >> W;
    for(int i = 0; i < T; i++){
        cin >> jadu[i];
        jadu[i] -= 1;
    }
    memset(dp, -1, sizeof(dp));
    
    cout << solve(0, 0, 0);
    
    return 0;
}