[백준] 14501번 퇴사

문제

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

풀이

삼성 기출문제 중에 난이도가 낮은 편에 속하는 것 같다.

N의 범위가 작기 때문에 완전탐색으로 풀었다.

오늘 예약된 상담을 진행하느냐 안하느냐 두 가지로 나누어서 재귀호출을 진행하면 된다.

계속 재귀함수의 조건이 헷갈려서 많이 틀렸다.

curr_day 가 n일 때 끝내는 이유는 curr_day가 n-1이고 상담에 걸리는 기간이 1일이면 하루만에 끝내고 수익을 얻을 수 있기 때문이다.

소스코드

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

using namespace std;

#define MAX_SIZE 16

int n;
int ans;
vector<pair<int, int>> vec_tp(MAX_SIZE, make_pair(0, 0));

void Recur(int curr_day, int curr_sum)
{
    // 끝나는 경우
    if (curr_day == n )
    {
        ans = max(ans, curr_sum);
        return;
    }

    int next_day = curr_day + vec_tp[curr_day].first;

    // 오늘 상담 하는 경우
    if (next_day <= n)
        Recur(next_day, curr_sum + vec_tp[curr_day].second);
    // 오늘 상담 안하는 경우
    if (curr_day + 1 <= n) 
        Recur(curr_day + 1, curr_sum);

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> vec_tp[i].first >> vec_tp[i].second;
    }

    Recur(0, 0);

    cout << ans << "\n";

    return 0;
}