BOJ 14501 퇴사

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

14501번: 퇴사

문제 해결전략

주로 DFS 또는 DP를 이용하는 문제이다.

DFS(완전 탐색)을 이용하여 해결하였다.

처음에는 day를 순차적으로 1->2->3->4->5->6->7->8까지 보내고, 7부터 차례대로 7->6->5->4->3->2->1 내려오면서 조건 확인과 계산(재귀)을 시작한다. 그림으로 간단히 표현하면 다음과 같다. (종료 조건은 N+1이다.)

 

#include <iostream>
using namespace std; 
int n;
int t[16];
int p[16];
int maxNum;
int max(int a, int b){ return a > b ? a : b; }
void dfs(int day, int sum){
    if(day == n + 1){
        maxNum = max(maxNum, sum); 
        return;
    }
    dfs(day + 1, sum);
    if(t[day] + day <= n + 1) dfs(t[day] + day, sum + p[day]);
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> t[i] >> p[i];
    }
    dfs(1, 0);
    cout << maxNum << endl;
}