입력 : 퇴사까지 남은 날짜 N, 상담 일정표
출력 : 백준이가 받을 수 있는 최대 수익
풀이
1. 다이나믹 프로그래밍의 전형적인 문제이므로 재귀함수 하나, 캐시테이블 하나를 정의해둔다.
2. 기저조건 : 업무기간이 N일을 넘어갈 경우 수익이 발생할 수 없음으로 0을 반환하도록한다.
3. 각 날짜에 잡힌 상담을 할 경우와 안할 경우를 비교해 더 큰 쪽을 리턴
->점화식 : C(i) = max( C(i+1), C(i+T[i]) + P[i] )
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 |
#include <algorithm>
#include <iostream>
using namespace std;
int T[20];
int P[20];
int cache[20];
int n;
int consult(int num){
if(num >= n)
return 0;
if(cache[num] == 0){
if(num + T[num] > n)
cache[num] = consult(num+1);
else
cache[num] = max(consult(num+1), consult(num+T[num]) + P[num]);
}
return cache[num];
}
int main() {
cin>>n;
for(int i=0; i<n; i++)
cin>>T[i]>>P[i];
cout<<consult(0)<<endl;
return 0;
} |
cs |
'개발 > 알고리즘' 카테고리의 다른 글
백준 알고리즘 14889 (0) | 2019.02.19 |
---|---|
백준 알고리즘 14500 (0) | 2019.02.19 |
백준 알고리즘 13458 (0) | 2019.02.16 |
백준 알고리즘 11931 (0) | 2019.02.15 |
백준 알고리즘 14499 (0) | 2019.02.15 |