BOJ 15486 퇴사 2

 

문제 링크 : https://www.acmicpc.net/problem/15486

15486번: 퇴사 2

 

상담원이 비서를 두고 있다는 사실에 매우 충격을 받은 문제였다.

 

dp 의 정의를 어떻게 하는가는 옳다는 것을 확인하기 전까지는 항상 어렵다.

1. 여기서는 dp[i] 를 ( i-1 ) 번째 일까지 끝난 상담에 대한 금액의 최댓값으로 정의한다. 

(현실에서는 선불로 받는다 하더라도)

 

2. dp[i] 은 최소한 dp[i-1] 을 물려받는다.

수익은 기본적으로 누적 개념이므로 그 전날까지 벌어들인 금액은 그 다음 날에 포함되어야 한다.

 

#include<bits/stdc++.h>

using namespace std;
const int MaxN=1500002;

int dur[MaxN],cst[MaxN], dp[MaxN];

int main(){
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&dur[i],&cst[i]);
    
    for(int i=1;i<=n;i++){
        dp[i+1]=max(dp[i],dp[i+1]);
        int x=i+dur[i];
        if(x<=n+1) dp[x]=max(dp[x], dp[i]+cst[i]);
    }
    
    printf("%d\n", dp[n+1]);
}

 

이번에는 탑다운 방식으로 해결해 보자.

아래 코드에서 dp[i] 는 i 번째 날부터 퇴사할 때까지 최대의 수익이다.(bottom up 과 방향이 반대)

 

#include<bits/stdc++.h>

using namespace std;
const int MaxN=1500002;

int N, dur[MaxN], cst[MaxN], dp[MaxN];

int recur(int i){
    if(i==N+1) return 0;
    int &ret=dp[i];
    if(ret!=-1) return ret;
    
    ret=0;
    ret=max(ret, recur(i+1));
    if(i+dur[i]<=N+1)
        ret=max(ret,cst[i]+recur(i+dur[i]));
    return ret;
}

int main(){
    scanf("%d",&N);
    memset(dp, -1, sizeof dp);
    
    for(int i=1;i<=N;i++)
        scanf("%d%d",&dur[i],&cst[i]);
    
    printf("%d\n", recur(1));
}