[BOJ] 15486 - 퇴사 2

1. 문제 해석

https://www.acmicpc.net/problem/15486

15486번: 퇴사 2

•  N일 동안 최대한 많은 일을 하려고 한다. ( 1 <= N <= 15000000)

•  상담을 완료하는데 걸리는 시간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi가 주어진다.

•  i 일에 상담을 하면 Ti 일 동안 상담을 하고 Pi 만큼의 금액을 받게 된다.

 

2. 접근 방법

•  d[i] = i일까지 지났을 때 상담으로 얻은 최대 이익

•  N - 1부터 0까지 반복하면서 d[i]를 구한다.

•  d[i + 1]와 d[i - t[i]] + p[i] 중에 더 큰 값이 d[i] 값이 된다.

•  i - t[i] - 1 < N 일 경우 d[i] = d[i + 1] 이된다.(남은 날이 t[i] 보다 작은 경우는 상담을 할 수 없기 때문)

 

 

3. 주의할 점

•  d[i]는 상담을 했을 경우와 상담을 안했을 경우 중 최대 값을 의미한다. 따라서 d[0]은 상담으로 얻을 수 있는 최대 값이다.

•  처음에는 0부터 N - 1까지 반복하며 d[i] 값을 구하려고 했으나 d[i]에서 일을 했을 경우를 처리하는 부분이 좀 더 까다롭다고 판단했다.그래서 N - 1부터 구하는 방식으로 구현하였는데 생각해보니 0부터 d[i]를 구해도 동일한 원리다.

 

4. 소스코드

#include <iostream>
using namespace std;
 
int N;
int t[1500001];
int p[1500001];
int d[1500001];
 
int main() {
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> t[i] >> p[i];
    }
 
    for (int i = N - 1; i >= 0; i--) {
        int col = i + t[i] - 1;
        if (col < N) {
            if (d[i + 1] < d[col + 1] + p[i]) {
                d[i] = d[col + 1] + p[i];
            }
            else {
                d[i] = d[i + 1];
            }
        }
        else {
            d[i] = d[i + 1];
        }
    }
 
    cout << d[0] << endl;
 
    return 0;
}