https://www.acmicpc.net/problem/14501
14501번: 퇴사
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
www.acmicpc.net
N의 범위가 1부터 15이므로 완전 탐색으로 쉽게 풀어줄 수 있다.
1부터 N까지의 날짜에 대해 해당 날짜에 상담을 하는 경우와 하지 않는 경우의 금액을 모두 계산하여 최댓값을 구한다.
주의 할점은 상담할 날로부터의 상담일수가 퇴사하는 날을 넘어가면 안된다.
이부분의 처리만 잘 해주면 된다.
자세한 설명은 아래 코드에서!
|
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
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <cstdio>
using namespace std;
int n;
int max;
int t[16];
int p[16];
void solve(int index, int sum) {
if(index > n) {
//퇴사하는 날짜가 되었으면 최댓값을 계산
if(max < sum) {
max = sum;
}
return;
}
//index번째 날짜에 상담을 하지 않는 경우
solve(index+1,sum);
//퇴사하는 날(n+1)을 넘어가지 않는 경우에만 index번째 날 상담을 진행
if(index+t[index] <= n+1)
//상담에 소요되는 날짜와 수익을 더해서 넘겨준다
solve(index+t[index],sum+p[index]);
}
int main() {
scanf("%d", &n);
for(int i=1; i<=n; i++) {
scanf("%d %d", &t[i],&p[i]);
}
max = 0;
solve(1,0);
printf("%d", max);
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 2206. 벽 부수고 이동하기 (0) | 2019.06.28 |
|---|---|
| [BOJ] 3055. 탈출 (0) | 2019.06.27 |
| [BOJ] 1697. 숨바꼭질 (0) | 2019.06.27 |
| [BOJ] 7569. 토마토 (3차원) (0) | 2019.06.27 |
| [BOJ] 7576. 토마토 (0) | 2019.06.27 |