BOJ 15486. 퇴사 2

 

문제 링크 

 

문제 풀이

 이 문제는 $N \leq 1.5\times 10^6$일 동안 상담을 하는데 각 상담마다의 걸리는 시간과 얻을 수 있는 금액이 주어질 때 얻을 수 있는 최대 금액을 출력하는 문제이다. 상담을 하는 기간이 서로 겹치면 동시에 할 수 없기 때문에 적절한 상담들만 선택해주어야 한다. 

 

 문제를 보자마자 DP가 떠올랐다. 그런데 시작 날짜를 기준으로 DP를 하면 망할 것이 뻔히 보이기 때문에 상담 종료 날짜를 기준으로 DP를 할 생각을 쉽게 할 수 있다. 그러기 위해서 종료 날짜를 기준으로  각 상담들을 정렬해주고 상담의 시작날짜와 종료날짜를 이용해 선분처럼 표현하면 라인 스위핑을 하면서 DP를 해주면 풀릴 것이다.

 

 점화식을 다음과 같이 정의하자. $dp[i] := (i$일 까지 상담을 통해 얻을 수 있는 최대 금액$)$. 상담 시작 날짜를 startTime, 상담 종료 날짜를 endTime, 얻을 수 있는 금액을 cost라고 하면 다음과 같은 관계식을 얻을 수 있다.

 

$$dp[endTime] = max(dp[endTime-1], cost + dp[startTime-1])$$

 

 이를 이용해서 코드만 잘 짜주면 된다.

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int NMAX = 1500000;

int N; 
vector<pair<int,pair<int,int>>> lines;
int dp[NMAX+1];

void input(){
    cin>>N;
    for(int i=0;i<N;i++){
        int duration,endTime,cost;
        cin>>duration>>cost;
        endTime = duration + i;
        lines.push_back({endTime,{duration,cost}});
    } 
}

void sweeping(){ 
    sort(lines.begin(),lines.end());
    
    int iter = 0; 
    for(int day=1;day<=N;day++){
        dp[day] = dp[day-1];
        while(lines[iter].first==day && iter < N){
            int duration = lines[iter].second.first; 
            int startTime = lines[iter].first - duration + 1; 
            int cost = lines[iter].second.second;
            dp[day] = max(dp[day],cost + dp[startTime-1]);
            
            iter++;
        }
    }
} 

void output(){
    cout<<dp[N];
} 
    
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0); 
    
    input(); 
    sweeping();
    output();
}