[백준/BOJ] 14501번 퇴사 (C++)

www.acmicpc.net/problem/14501

14501번: 퇴사

삼성 역량 테스트 기출 문제 : DP or DFS

입력값의 범위가 크다면 DP를 이용해야겠지만, 최대 15이기 때문에 DFS를 이용한 완전 탐색으로 모든 경우의 수를 구하고 그 중에 최대인 경우를 구하는 것도 가능합니다. 둘다 핵심은 상담 날짜를 예약하는 경우와 예약하지 않는 경우 두 가지 케이스를 고려하는 것입니다.

 

#include <iostream>
#include <vector>
using namespace std;

int n, answer;
vector<pair<int, int > > v;

void DFS(int day, int sum) {
    if(day == n + 1) {
        answer = max(answer, sum);
        return;
    } else {
        // 상담 날짜를 예약하는 경우
        // 현재 날짜 + 상담 기간 <= 퇴사 날짜
        if(day + v[day].first <= n + 1) {
            DFS(day + v[day].first, sum + v[day].second);
        }
        
        // 상담 날짜를 예약하지 않는 경우
        DFS(day + 1, sum);
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n;
    // 1번 인덱스부터 사용하기 위해서 0번 인덱스에 아무값이나 넣어줌
    v.push_back({0, 0});
    for(int i = 0; i < n; i++) {
        int day, cost;
        cin>>day>>cost;
        v.push_back({day, cost});
    }

    DFS(1, 0);
    cout<<answer;
} 

 

#include <iostream>
using namespace std;

int day[16];
int cost[16];
int dp[16];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, answer = 0;
    cin>>n;
    
    for(int i = 1; i <= n; i++) {
        cin>>day[i]>>cost[i];
    }
    
    for(int i = 1; i <= n; i++) {
        int getBooked = i + day[i]; // 상담 날짜를 예약하는 경우
        int notBooked = i + 1; // 상담 날짜를 예약하지 않는 경우
        
        // 퇴사 날짜 전 일때, 각각의 경우에 최대값을 기록
        if(getBooked <= n + 1) dp[getBooked] = max(dp[getBooked], dp[i] + cost[i]);
        if(notBooked <= n + 1) dp[notBooked] = max(dp[notBooked], dp[i]);
        
        // 최종적으로 dp[n + 1]의 최대값을 구하게 된다.
        answer = max(max(answer, dp[getBooked]), dp[notBooked]);
    }
    
    cout<<answer;
}