이 문제는.. 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
47
48
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
#include <vector>
#include <functional>
 
#define MAX_SIZE 16
#define INF 0x7fffffff
 
using namespace std;
//input
int cost[MAX_SIZE];
int day[MAX_SIZE];
int n;
 
//process
int max_value;
 
void input(){
    scanf("%d"&n);
 
    for (int i = 1; i <= n; i++scanf("%d %d"&day[i], &cost[i]);
}
 
void dfs(int d, int sum){
    if (d == n + 1){
        max_value = max(max_value, sum);
        return;
    }
 
    if(d + day[d] <= n + 1) dfs(d + day[d], sum + cost[d]);
    if(d + 1 <= n + 1) dfs(d + 1, sum);
}
 
void process(){
    dfs(10);
    printf("%d\n", max_value);
}
 
int main(){
    input();
    process();
 
    return 0;
}
cs



디피로도 한번 풀어봤는데..

더 효율적인 점화식이 있다면 댓글 부탁드립니다.


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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
#include <vector>
#include <functional>
 
#define MAX_SIZE 51
#define INF 0x7fffffff
 
using namespace std;
 
int day[MAX_SIZE];
int cost[MAX_SIZE];
int dp[MAX_SIZE];
 
int main(){
 
    int n;
    scanf("%d"&n);
    for(int i = 1; i <= n; i++scanf("%d %d"&day[i], &cost[i]);
 
    int ret = 0;
    for(int i = 1; i <= n; i++){
        int next1 = i + day[i];
        int next2 = i + 1;
 
        if(next1 <= n + 1) dp[next1] = max(dp[next1], dp[i] + cost[i]);
        if(next2 <= n + 1) dp[next2] = max(dp[next2], dp[i]);
 
        ret = max(max(ret, dp[next1]), dp[next2]);
    }
 
    printf("%d\n", ret);
 
    return 0;
}
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[14503] 로봇 청소기  (2) 2017.04.18
[14502] 연구소  (5) 2017.04.18
[14500] 테트로미노  (0) 2017.04.17
[3055] 탈출  (0) 2017.04.16
[5427] 불  (0) 2017.04.16

+ Recent posts