백준[14501] 퇴사

삼성 SW역량테스트 문제이다

링크 : https://www.acmicpc.net/problem/14501

이 문제는 DP로도 풀수있고 점화식이 잘 안보인다면 재귀탐색으로 해결할 수 있다. 시간과 값이 있을 때, 가능한 최대값을 구하는 문제이다.

필자는 DP로 푼 답은 이해가 잘 가지않고 점화식도출이 쉽게 되지않아 재귀를 사용하여 해결하였다. N+1일째 결과를 return하는것이 중요하다.

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<stack>
#include<queue>
 
using namespace std;
 
int n, arrt[16], arrp[16],ans;
 
void dfs(int a, int b) {
    //printf("%d\n", a);
    if (a > n + 1) return;
    if (a == n+1) {
        ans = max(ans, b);
        return;
    }
    dfs(a + 1, b);
    dfs(a + arrt[a], b + arrp[a]);
}
 
int main(void)
{
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d %d", &arrt[i], &arrp[i]);
    dfs(1, 0);
    printf("%d", ans);
    return 0;
}