[삼성 SW 기출 문제/1일차] 14501 퇴사(dfs, DP)

1. dfs 풀이

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N;
int T[20];
int P[20];
int ans = 0;

int dfs(int cur, int curRevenue){
    // 종료 조건
    if(cur >= N){
        ans = max(ans, curRevenue);
        return ans;
    }
    
    if(cur + T[cur] < N){ // 상담 진행 시
        dfs(cur+T[cur], curRevenue+P[cur]);
    }
    dfs(cur+1, curRevenue); // 상담 X
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> T[i] >> P[i];
    }
    cout << dfs(0, 0);
    
}

2. DP 풀이

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N;
int T[20];
int P[20];
int dp[20] = {0};
int ans = 0;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> T[i] >> P[i];
    }
    // dp로 풀이하기
    for(int i = N-1; i >= -1; i--){
        if(i + T[i] <= N) { // 상담을 진행할 수 있다면
            dp[i] = max(dp[i+1], dp[i + T[i]] + P[i]);
        }
        else dp[i] = dp[i+1]; // 상담 진행 불가할 때
    }
    cout << dp[0];
}