quit2-15486

• toc {:toc}

문제 확인하기

풀이

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200

해당 예시를 통해서 확인해보면 결국 계속해서 누적으로 최대의 수익을 내도록 만들어야 한다.
어떤 날부터 시작할 지를 모르기 때문에 전체적으로 확인해줘야 한다. 해당 예시에서 최대는 1일, 4일, 5일의 경우 45로 최대가 된다.

최댓값을 계속해서 갱신을 하기 위해서 해당 시점의 최댓값을 res로 dp에 갱신해준다. 상담을 진행할 때 수익을 받는 시점은 상담을 T일 동안 진행한 후 얻을 수 있기 때문에 끝난 시점의 dp에 저장해주고, 최댓값을 갱신하는 방식으로 dp를 갱신해나간다.

• 1일 상담 진행

	1일	2일	3일	4일	5일	6일	7일
dp	0	0	0	10	0	0	0

res = 0

• 2일 상담 진행

	1일	2일	3일	4일	5일	6일	7일
dp	0	0	0	10	0	0	20

res = 0

• 3일 상담 진행

	1일	2일	3일	4일	5일	6일	7일
dp	0	0	0	10	0	0	20

res = 0

3일 상담의 경우 3일 하루 상담을 진행하고 4일에 수익을 얻는다. 이 때 얻은 수익이 이전에 얻을 수 있었던 수익보다 높은지 낮은지를 확인하고, 높으면 갱신, 낮으면 통과한다.

• 4일 상담 진행

	1일	2일	3일	4일	5일	6일	7일
dp	0	0	0	10	30	0	20

res = 10

4일 상담을 진행하면 4일 하루 상담을 진행하고 5일에 수익 +20이 된다. 이 때, 이전에 얻었던 수익을 추가해줘야 하기 때문에 dp[5]에서 dp[4]의 값과 4일 상담을 진행하고 난 뒤의 수익 20을 더해 30을 저장한다.

• 5일 상담 진행

	1일	2일	3일	4일	5일	6일	7일
dp	0	0	0	10	30	0	45

res = 30

5일 상담을 진행하면 이틀을 진행해야 하기 때문에 dp[7]에 수익이 저장된다. +15를 통해 45를 저장한다. 이 때도 이전에 얻을 수 있었던 수익보다 높은지 낮은지를 확인하고 높으면 갱신, 낮으면 통과시킨다.

• 6일 상담 진행

	1일	2일	3일	4일	5일	6일	7일
dp	0	0	0	10	30	30	45

res = 30

6일의 경우 8일에 퇴사를 해야하는데 4일 동안 상담할 수 없기 때문에 통과시킨다. n+1일보다 큰 경우 통과시키는 조건을 추가해야 한다. 수익을 얻을 수 있는 여러 가지 경우의 수 중 최대 수익을 얻는 경우의 수를 선택하기 위해서 최댓값을 dp에 계속 갱신을 해줘야 하기 때문에 dp[6]에도 최댓값인 res=30을 저장한다.

• 7일 상담 진행

7일의 경우에도 상담을 할 수 없기 때문에 dp값은 변하지 않는다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
 
int T[1500005], P[1500005], res=0;
int dp[1500005];
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int n;
 
    cin >> n;
 
    for(int i=1; i<=n; i++){
        cin >> T[i] >> P[i];
    }
 
    for(int i=1; i<=n+1; i++){
        dp[i] = max(dp[i], res);
        if(i+T[i] < n+1 && dp[i]+P[i] > dp[i+T[i]]){
            dp[i+T[i]] = dp[i] + P[i];
        }
        res = max(dp[i], res);
    }
 
    cout << res << endl;
 
    return 0;
}