본문 바로가기

개발/알고리즘

백준 알고리즘 14501

 

입력 : 퇴사까지 남은 날짜 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