[백준 15486번] 퇴사 2 (C++)

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

15486번: 퇴사 2

---

본 게시글은 BJ 14501 퇴사, 15486 퇴사2를 참고하여 작성되었습니다.

 

퇴사 2 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다.

 

다이나믹 프로그래밍의 테이블 d[i]는 i번째 일까지 상담했을 때 얻는 최대 이익으로 정의하였습니다.

 

i번째 상담 종료되는 날에, i번째 일까지 상담했을 때 얻는 최대 이익 + i번째 상담의 비용을 기록하면 됩니다. 

단, 테이블에 이미 수익이 기록되어 있는 경우는 다른 상담 경로가 기록한 수익이므로, 더 많은 수익을 내는 것을 기록해주면 됩니다. 

 

아래는 테스트케이스입니다.

	1일	2일	3일	4일	5일	6일	7일
걸리는 기간	3	5	1	1	2	4	2
비용	10	20	10	20	15	40	200

 

테이블을 채우는 과정은 아래와 같습니다.

N일째의 상담 기간이 1인 경우, 수익은 N + 1일에 기록해야므로, 테이블의 길이는 N + 1입니다.

일수	1일	2일	3일	4일	5일	6일	7일	8일
최대 이익	0	0	0	10	0	0	0	0

1일째의 상담 기간이 3일이므로, d[4]에 10을 기록해줍니다.

 

일수	1일	2일	3일	4일	5일	6일	7일	8일
최대 이익	0	0	0	10	0	0	20	0

2일째의 상담 기간이 5일이므로, d[7]에 10을 기록해줍니다.

 

일수	1일	2일	3일	4일	5일	6일	7일	8일
최대 이익	0	0	0	10	0	0	20	0

3일째의 상담 기간이 1일이므로, d[4]에 10을 기록해주어야 하지만, 이미 10이 기록되어 있으므로, 기록하지 않습니다.

 

일수	1일	2일	3일	4일	5일	6일	7일	8일
최대 이익	0	0	0	10	30	0	20	0

4일째의 상담 기간이 1일이므로, d[5]에 30을 기록해줍니다. 

 

일수	1일	2일	3일	4일	5일	6일	7일	8일
최대 이익	0	0	0	10	30	0	45	0

5일째의 상담 기간이 2일이므로, d[7]에 45를 기록해줍니다. (45 > 20이므로)

 

일수	1일	2일	3일	4일	5일	6일	7일	8일
최대 이익	0	0	0	10	30	30	45	0

d[6]은 0입니다. 하지만, 5일째까지 상담 했을 때 최대 이익이 30이므로, d[6]에 30을 기록해줍니다. (만약, d[6]이 d[5]보다 작은 경우

d[6]은 d[5]가 되어야합니다.)

또한, 6일째의 상담 기간은 4일이므로, 기간 내에 상담을 완료할 수 없으므로 기록하지 않습니다.

 

일수	1일	2일	3일	4일	5일	6일	7일	8일
최대 이익	0	0	0	10	30	30	45	0

마찬가지로, 7일째의 상담 기간은 2일이므로, 기간 내에 상담을 완료할 수 없으므로 기록하지 않습니다.

 

아래는 Bottom-Up 방식의 다이나믹 프로그래밍 코드입니다.

#include <bits/stdc++.h>
using namespace std;

#define period first 
#define cost second 

pair<int, int> arr[1500010];
int n, d[1500010]; // i번째 일까지 상담했을 때 얻는 최대 이익

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);     

    cin >> n;
    // 각 상담을 완료하는데 걸리는 기간과 받을 수 있는 금액을 입력 받음
    for(int i = 1; i <= n; i++) cin >> arr[i].period >> arr[i].cost;    

    // Bottom-Up Dynamic programming
    for(int i = 1; i <= n; i++){    
        // d는 i번째 일까지 상담했을 때 얻는 최대 이익이므로, 기존의 최대 이익이 이어짐 
        if(d[i] == 0) d[i] = d[i - 1];  
        else d[i] = max(d[i], d[i - 1]);

        if(d[i + arr[i].period] == 0)   // i번째 상담이 종료되는 날에 수익을 기록
            d[i + arr[i].period] = d[i] + arr[i].cost;  // i번째 일까지 상담했을 때 얻는 최대 이익 + i번째 상담의 비용
        else    // 이미 수익이 기록되어 있는 경우 
            d[i + arr[i].period] = max(d[i] + arr[i].cost, d[i + arr[i].period]); // 더 많은 수익을 기록
    }

    cout << *max_element(d + 1, d + n + 2);
}