[Algorithm] 퇴사하겠습니다 BOJ 14501(퇴사)

문제 정의

• N일 동안 일을 했을 때 최대 수익을 구하는 프로그램을 작성하시오.
• N+1일에 무조건 퇴사한다
• 상담을 진행하는 경우 해당 일자의 수익을 얻지만 그 만큼의 시간도 소요된다.

문제 해결 전략

이 문제를 한 큐에 해결할 수 있는 재귀함수를 설계하고자 한다. 재귀함수는 간단한 표현으로 모든 경우의 수를 실행시킬 수 있는 강력한 특성을 지니고 있다.

재귀함수 설계 조건

다음과 같은 조건을 반드시 고려하고 설계해야한다.

• 진행이 불가능한 경우에 대한 예외 처리
• 정답인 경우 탈출 조건 수행
• 재귀함수 수행, 정답이 될 때까지

재귀함수 설계: rMax 함수

위와 같은 조건을 고려하여 다음과 같은 함수를 설계하고자 한다.

• 진행이 불가능한 경우: 상담을 진행하고 종료일이 퇴사일(N일)을 넘어설 때
• 정답인 경우: 상담 종료 시점 혹은 시간이 지났을 때 퇴사일(N일)일때
• 재귀함수 수행: 그 날 상담을 할 수 있고, 상담을 안 할 수 있다.

각 날짜의 상담을 진행했을 때 걸리는 시간을 vector days에 담고 이 날 상담을 진행할 때 벌 수 있는 수익을 vector profits에 담았다고 할 때, 다음과 같은 함수를 설계할 수 있다.

void rMax(const vector<int>& days, const vector<int>& profits, 
  const int& n, int day, int profit)
{
  	//정답인 경우, 만약 profit이 기존 max값보다 클 경우 max 값 교체(max는 전역변수겠지)
    if(day == n){
        if(mMax < profit)
            mMax = profit;
        return;
    }
    //불가능한 경우, 그냥 함수 종료
    if(day > n){
        return;
    }
    
  	//상담을 진행안 할 경우, 하루를 흘려보내고 이익 유지
    rMax(days, profits, n, day + 1, profit);
  	//상담을 진행할 경우, 수익을 벌고 날짜도 그만큼 보내야됨
    rMax(days, profits, n, day + days[day], profit + profits[day]);
}

전체 코드

#include <iostream>
#include <vector>

using namespace std;
int mMax = 0;

void rMax(const vector<int>& days, const vector<int>& profits, const int& n, int day, int profit)
{
  if(day == n){
      if(mMax < profit)
          mMax = profit;
      return;
  }
  if(day > n){
      return;
  }
  
  rMax(days, profits, n, day + 1, profit);
  rMax(days, profits, n, day + days[day], profit + profits[day]);
}

int main()
{
  vector<int> days;
  vector<int> profits;
  int n;
  cin >> n;
  for(int i=0; i<n; i++)
  {
      int day, profit;
      cin >> day >> profit;
      days.push_back(day);
      profits.push_back(profit);
  }

  rMax(days, profits, n, 0, 0);
  cout << mMax << endl;
  return 0;
}