백준 14501: 퇴사

문제

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

문제를 보면 DP로 풀 수 있다는 것을 알 수 있습니다.

검색을 해본 결과 DFS로도 풀 수 있다는 것을 알게되었습니다.

문제를 풀때 꼭 한 방법만이 아닌 다른 방법도 생각하는 습관을 들이는 것이 좋을것 같습니다.ㅎㅎ;;

이 문제는 상담을 하거나 안하거나 둘중 하나를 고르는 것이 관건인 문제입니다.

DP의 경우는 점화식을 세워서 문제를 풀며, 점화식은 max(dp(day+1), dp(day+T[day])+P[day]) 입니다.

전자 의 경우는 상담을 안 하였을때의 식이며, 후자의 경우는 상담을 하였을 때의 식입니다.

T[day]는 해당 날짜의 상담을 했을 경우 걸리는 시간이며, P[day]는 그에 따른 보수입니다.

DFS 경우에도 DP와 똑같은 식을 사용하여 풀었습니다.

모든 경우의 수를 다 해보아도 퇴사날의 크기가 작기 때문에 시간상으로도 문제가 되지 않습니다.

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int D[16];
int T[16];
int P[16];
int n;
int ans;
 
//dp의 경우
int dp(int day){
    if(day == n+1) return 0;
    //날짜가 n+1보다 크다면 -값을 크게 준다.
    if(day > n+1) return -987654321;
    //메모이제이션
    if(D[day] > 0) return D[day];
    //점화식 상담을 안한다 혹은 상담을 한다. 둘 중 하나를 고른다.
    return D[day] = max(dp(day+1), dp(day+T[day])+P[day]);
}
//dfs의 경우(모든 경우를 해본다.)
void dfs(int day, int sum){
    if(day == n+1){
        ans = max(ans, sum);
        return;
    }
    //상담을 안하는 경우
    dfs(day+1, sum);
    //상담을 할 수 있을 경우는 상담을 한다.
    if(day+T[day] <= n+1)
        dfs(day+T[day], sum+P[day]);
}
 
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> T[i] >> P[i];
    cout << dp(1)<<"\n";
    dfs(1,0);
    cout << ans <<"\n";
    return 0;
}