[백준/Baekjoon] 2240 자두나무 C++ :: Dynamic Programming

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

2240번: 자두나무

---

1. Logic

먼저 DP테이블이 의미하는 것은 n초에 먹을 수 있는 자두의 최대 갯수이다.

dp[자두떨어지는 시간][움직인횟수][위치한나무번호]

 

부분문제를 쪼개보자면

 

시작할때는 

1. 1번 나무에서 시작하는 경우

2. 2번 나무에서 시작하는 경우

 

이후에는 

1-1. 1번나무에서 받아먹고 계속 1번에 있는 경우

1-2. 1번나무에서 받아먹고 2번나무로 옮기는 경우

2. 2번나무에서 받아먹고 계속 2번에 있는 경우

2. 2번 나무에서 받아먹고 1번 나무로 옮기는 경우

이렇게 4가지가 있는데 여기서 해당 나무의 번호와 지금 떨어지는 자두의 나무가 일치했을 경우의 갯수만 세주면 된다.

---

2. Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int t, w;

int dp[1001][31][3];

vector<int> tree;

int solve(int cnt, int moveCnt, int treeNum) {
    if(cnt == t+1) return 0;
    
    int &ret = dp[cnt][moveCnt][treeNum];
    if(ret != -1) return ret;
    
    ret = 0;
    
    if(cnt == 0) {
        //원래 1의 자리에서 시작
        ret = max(ret, solve(cnt+1, moveCnt, 1));
        // 2의 자리로 옮겨서 시작
        ret = max(ret, solve(cnt+1, moveCnt+1, 2));
    }
    else {
        if(tree[cnt] == treeNum) {
            ret = max(ret, solve(cnt+1, moveCnt, treeNum) + 1);
            if(treeNum == 1 && moveCnt+1 <= w) {
                ret = max(ret, solve(cnt+1, moveCnt+1, 2)+1);
            }
            else if(treeNum == 2 && moveCnt+1 <= w){
                ret = max(ret, solve(cnt+1, moveCnt+1, 1)+1);
            }
        }
        else {
            if(treeNum == 1) {
                ret = max(ret, solve(cnt+1, moveCnt, 1));
            }
            else {
                ret = max(ret, solve(cnt+1, moveCnt, 2));
            }
        }
        
        if(treeNum == 1 && moveCnt+1 <= w) {
            ret = max(ret, solve(cnt+1, moveCnt+1, 2));
        }
        else if(treeNum == 2 && moveCnt+1 <= w){
            ret = max(ret, solve(cnt+1, moveCnt+1, 1));
        }
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(dp, -1, sizeof(dp));
    
    cin >> t >> w;
    
    tree.push_back(-1);
    
    for(int i = 0; i < t; i++) {
        int tr;
        cin >> tr;
        
        tree.push_back(tr);
    }
    
    cout << solve(0, 0, 1);
}

---

3. Feedback

골드 5짜리 DP를 혼자 풀었다!! 역시 꾸준함의 힘은 대단하다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐