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;
}