퇴사

코드

[ 완전 탐색 코드 ]

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#define ll long long
#define ull unsigned long long
using namespace std;
// 1:24 ~ 1:49
int N,ans;
vector<pair<int,int>> v;
void DFS(int depth, int left, int sum){
    if(depth >= N) return;
    for(int i=depth;i<N;i++)
    {
        left--;
        if(left > 0) continue;
        if(i+v[i].first > N) continue;
        ans = max(ans, sum+v[i].second);
        DFS(i+1, v[i].first, sum+v[i].second);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(int i=0;i<N;i++)
    {
        int a,b;
        cin >> a >> b;
        v.push_back({a,b}); // 걸리는 날짜, 받는 금액
    }
    DFS(0, 0, 0);
    cout << ans;
    return 0;
}

• 핵심
  • DFS의 매개변수로 left를 전달해서 left가 0보다 작을 때 일을 하도록 설계
  • N이 15정도로 작기 때문에 충분히 완전탐색 으로 가능한 것을 캐치해야 함

---

[ DP 코드 ]

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#define ll long long
#define ull unsigned long long
using namespace std;
int N,ans;
// DP[i] = i일 전 까지 일했을 때 받는 최대 금액
int DP[20];
vector<pair<int,int>> v;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    v.push_back({-1,-1});
    for(int i=0;i<N;i++)
    {
        int a,b;
        cin >> a >> b;
        v.push_back({a,b}); // 걸리는 날짜, 받는 금액
    }
    /* DP[i] = i일 전까지 일했을 때 얻는 최대 금액 */
    for(int i=2;i<=N+1;i++)
    {
        int MAX=0;
        for(int j=1;j<i;j++)
        {
            if(j+v[j].first <= i)
                MAX = max(DP[j] + v[j].second, MAX);
        }
        DP[i] = MAX;
    }
    /* DP[N+1] = N+1일 전까지 일했을 때 얻는 최대 금액 
               = N일 까지 일했을 때 얻는 최대 금액 */
    cout << DP[N+1];
    return 0;
}

• 로직
  • DP[i] = i일 전까지 일했을 때 얻는 최대 금액
  • DP[i]는 1일 ~ i-1일에 주어진 일을 할 때 i일 전에 끝낼 수 있다면 그 중 최대값을 의미
    ex)
    DP[4] = 1일 일을 했을 때, 2일 일을 했을 때, 3일 일을 했을 때 총 3가지 경우중 최대를 가짐
    DP[4] = max(DP[1]+v[1].second , DP[2]+v[2].second, DP[3]+v[3].second);

• 핵심
  : DP[i]를 i일 까지 일했을 때 로 잡을건지, i일 전 까지 일했을 때로 잡을것인지 확실하게 정해야 함

---