퇴사 2

코드

[ DP풀이 1번 ]

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 1059 ~ 1130
int N,ans;
int D[1500005];
vector<pair<int,int>> v(1500005);
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(int i=1;i<=N;i++)
    {
        int t,p;
        cin >> t >> p;
        v[i] = {t,p};
    }
    // D[i] = i-1일까지 일 했을 때 얻는 최대 금액
    /* 오래걸리는 최대 일수는 50이니까 오늘 날짜부터 50일 전까지만 검사하면 된다고 생각함
       --> i-50이 아니라 i-53을 해야 정답처리가 되었다 --> 이유는 모르겠음
                                                   (어차피 시간은 충분하니 넉넉하게 -100해도 된다) */
    D[1] = 0;
    for(int i=2;i<=N+1;i++)
    {
        int val = 0;
        int st = i-53; // i-52는 오답처리 
        if(st < 1) st = 1;
        for(int j=st;j<i;j++)
        {
            if(j + v[j].first <= i)
                val = max(D[j]+v[j].second, val);
        }
        D[i] = val;
    }
    cout << D[N+1];
    return 0;
}

• DP 로직
  • D[i] = i-1일까지 일 했을 때 얻는 최대 금액
  • 최대 Ti가 50이라서 최대 D[i-50]을 검사하면 될 줄 알았음
    --> 실제로 D[i-53]부터 정답처리가 되었다 --> 이유는 모르겠음
    (어차피 시간도 넉넉하니 이럴때는 안전하게 -100정도 해도 괜찮을듯)

---

[ DP풀이 2번 ]

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
int N,ans;
int D[1500105]; // Ti최대가 50이니까 넉넉하게 +100만큼 더 잡아줘야 OutOfBounds오류 피할 수 있음
vector<pair<int,int>> v(1500005);
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(int i=1;i<=N;i++)
    {
        int t,p;
        cin >> t >> p;
        v[i] = {t,p};
    }

    /* D[i] = i-1일까지 일했을 때 받는 최대 금액 */
    for(int i=1;i<=N;i++)
    {
        D[i+v[i].first] = max(D[i+v[i].first], D[i]+v[i].second); // i번째 일을 했을 때 갱신
        D[i+1] = max(D[i+1], D[i]); // i번째에 일을 하지 않았으니 전값과 비교해 최대 갱신
    }
    cout << D[N+1];
    return 0;
}

• DP 로직
  • D[i] = i-1일까지 일했을 때 얻는 최대 금액
  • D[i+Ti] = max(D[i+Ti], D[i]+Pi)
    : 끝나는 날 값을 검사해서 바로 바로 갱신
  • D[i+1] = max(D[i+1], D[i])
    : D[i+1]일 값이 한번도 갱신되지 않았어도 이전 값으로 갱신되게 함