(C++) - 백준(BOJ) 14501번 : 퇴사

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

14501번: 퇴사

dp문제였습니다.

 

 

📕 풀이방법

 1. 두 가지 선택 방법이 있습니다. 현재 상담을 선택하는 경우와 현재 상담을 선택하지 않는 경우입니다. 현재 상담을 선택하는 경우 그만큼의 이익이 있지만 상담기간동안 다른 상담을 못한다는 기회비용이 존재합니다. 따라서 선택하거나 선택하지 않을 경우에 대해 저울질해서 이익의 최댓값을 찾아야 합니다.

 

 2. 현재 기간 + 현재 상담하기로 결정했을 때 걸리는 상담시간이 퇴사일보다 이하라면 현재의 상담을 하도록 선택할 수 있습니다. 점화식을 세워보면 다음과 같습니다. 먼저 d배열은 t일차에 얻을 수 있는 최대 이익입니다.

 

Top down 방식으로 구현

if(t + contTime <= n) //conTime은 t일차 상담시 소요시간입니다. price는 t일차 상담시 얻는금액입니다.

 d[t] = max(d[t], d[t + conTime] + price)

d[t] = max(d[t], d[t+1])

 

퇴사일 이하로 상담을 끝낼 수 있을 때 t일차의 상담을 하기로 결정하는 것, t일차의 상담을 하지 않는 것 두 가지의 max값으로 비교해가며 top down, bottom up 방식으로 구현했습니다. 

 

 

---

 

 

📕 Code

📔 top down

#include <bits/stdc++.h>
using namespace std;
struct Consulting { int conTime, price; };
int n, d[16];
vector <Consulting> c;

int dp(int t){
    if(t >= n) return 0;
    int &ret = d[t];
    if(ret != -1) return ret;
    ret = 0;
    if(t + c[t].conTime <= n)    
        ret = max(ret, dp(t + c[t].conTime) + c[t].price);
    ret = max(ret, dp(t+1));
    return ret;
}

int main(){
    memset(d,-1,sizeof(d));
    cin >> n;
    for(int i = 0,t,p; i < n; i++){
        cin >> t >> p;
        c.push_back({t,p});
    }
    cout << dp(0);
}

 

📔 bottom up : 개인적으로 bottom up dp가 훨씬 어려운 것 같습니다.

#include <bits/stdc++.h>
using namespace std;
struct Consulting {int conTime, price; };
int n, ans;
int d[16];

vector <Consulting> plan;
int main(){
    cin >> n;
    for(int i = 1,t,p; i <= n; i++){
        cin >> t >> p;
        plan.push_back({t,p});
    }
    for(int i = 0; i <= n; i++){
        d[i] = max(d[i],d[i-1]);
        if(i + plan[i].conTime <= n ){
            d[i+plan[i].conTime] = max(d[i+plan[i].conTime], d[i] + plan[i].price);
        }
    }

    for(int i = 1; i <= n; i++) ans = max(ans,d[i]);
    cout << ans;
}