[Problem Solving] BOJ 15486 : 퇴사 2

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

 

상담 소요 시간 테이블 T와 상담 수익 테이블 P가 주어졌을 때, N + 1일에 퇴사할 경우 얻을 수 있는 최대 수익을 구하는 프로그램을 만들면 된다. 우선 N의 최댓값은 1500000이기 때문에 O(N^2)인 알고리즘으로 만들면 시간초과가 무조건 난다. 이 문제는 DP를 사용하여 O(N)에 풀 수 있다.

 

우선 DP테이블을 정의하자면, DP[i]는 i번째 날 부터 일을 시작해서 퇴사할 경우 얻을 수 있는 최대 수익이다. DP[N]에서 DP[1] 순서로 구해서 DP[1]을 출력하면 된다.

i	1	2	3	4	5	6	7
T_i	3	5	1	1	2	4	2
P_i	10	20	10	20	15	40	200

 

1. DP테이블을 0으로 초기화한다.

2.

i + T[i]가 N + 1보다 작거나 같다면, 즉 i번째 날에 상담을 시작해서 퇴사 전날까지 마무리 할 수 있다면, DP[i]는 DP[i + 1] (i + 1번째 날 부터 일을 시작해서 퇴사할 경우 얻을 수 있는 최대 수익)과 DP[i + T[i]] + P[i] (i번째 날에 시작한 상담 후 다음 상담 일정으로 얻은 수익의 최댓값 + i번째 날 상담으로 얻는 수익)중 더 큰 값을 취한다.

i + T[i]가 N + 1보다 크다면, 즉 i번째 날에 상담을 시작해서 퇴사 전날까지 마무리 할 수 없다면, DP[i]는 DP[i + 1] (i + 1번째 날 부터 일을 시작해서 퇴사할 경우 얻을 수 있는 최대 수익)를 취한다.

3. 2 과정을 i = N부터 1까지 시행한다.

 

#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;

int N;
vector<int> T;
vector<int> P;
vector<int> dp;

void input()
{
    cin >> N;
    T.resize(N + 1);
    P.resize(N + 1);
    dp.resize(N + 2, 0);
    for(int i = 1; i <= N; i++)
    {
        cin >> T[i] >> P[i];
    }
}

void solution()
{
    for(int i = N; i >= 1; i--)
    {
        if(i + T[i] <= N + 1)
        {
            dp[i] = max(dp[i + 1], dp[i + T[i]] + P[i]);
        }
        else
        {
            dp[i] = dp[i + 1];
        }
    }
}

void output()
{
    cout << dp[1] << endl;
}
 
int main(void)
{
    input();
    solution();
    output();
    return 0;
}