[14501] 퇴사

이 문제는.. N이 작아서 그냥 완전 탐색으로 해결했습니다.

결국 그 날에 그 고객을 상담하냐 안하냐 이 두가지 경우 뿐입니다.

굉장히 난이도가 낮은 문제입니다.

#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(1, 0);
    printf("%d\n", max_value);
}
 
int main(){
    input();
    process();
 
    return 0;
}

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

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

#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;
}