[백준]14501번. 퇴사 문제 풀이

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

문제 정리: 상담 일정표를 참고하여 최대이익을 얻을 수 있는 상담을 하는 것이 목적.
                 퇴사날과 퇴사날 이후에 상담을 할 수 없음을 고려하여 문제를 풀어야한다.

 

문제 풀이: 최대이익을 얻기 위해 모든 경우의 수를 검사해야 함

-> 단순히 중첩 for문을 사용하면 for문이 수없이 많아짐.
->재귀함수를 이용한 완전 탐색을 해야한다.

 

#include <iostream>

using namespace std;

int N; //퇴사날은 N+1
int T_i[16];  //N의 최댓값은 15이지만, 1일과 T_i[1]를 같게 다루기 위해서 16으로
int P_i[16];
int max_val=0;

void calProfit(int workD,int sum,int before_add)
{
    if(workD == N + 1 ) //일 끝난 다음날이 퇴사날
    {
        max_val = max(max_val, sum);
        return ;
    } 
    else if (workD > N + 1){ //일 끝나는 날이 퇴사날을 넘음
        max_val = max(max_val, sum-before_add);
        return ;
    }
    //일을 시작할 날짜에 수행기간을 더한 것을 재귀적으로
    //더할때는 퇴사날을 무시하고 계산
    //i++로 1>5와 1>6 1>7를 완전탐색함
    for ( int i = workD + T_i[workD] ; i <= N + T_i[workD] ; i++)
        calProfit(i, sum + P_i[workD] , P_i[workD]);
}

int main()
{
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        cin>>T_i[i]>>P_i[i];
    }
    for(int i=1;i<=N;i++) //일하는 날의 시작값을 넣어줌
    {
        calProfit(i,0,0);
    }
    cout<<max_val;
    return 0;
}

 

 

문제 소감: 재귀함수에 대한 이해가 부족하여 for 완전탐색을 구현하는데 시간이 많이 걸렸다.
재귀를 사용하는 문제를 많이 풀어보진 않았지만 재귀함수는 void형식으로 하는 것이 구현에 용이해보인다.