알고리즘문제) 휴가(SW역량평가 기출)

문제

 

 

해결방법:

DFS를 이용하여 가장 높은 수익을 찾는다. 

 

 

코드

 

vector<pair<int,int>>vacation;
int day, T, P,_max=0,_minn=-1000;

void vacationDFS(int days)
{
    if (days == day+1)
    {
    	_minn=max(_minn,_max);
		return ;
    }
    else
    {
        int able =days+vacation[days].first;

        if (able <= day+1)
        {
            _max += vacation[days].second;
            vacationDFS(able);
            _max -= vacation[days].second;
        }
        vacationDFS(days+1);
 
    }
}



int main()
{

    cin >> day;
    vacation.push_back(make_pair(0, 0));
    for (int i = 0; i < day; i++)
    {
        cin >> T >> P;
        vacation.push_back(make_pair(T,P));
    }

    vacationDFS(1);

    cout << _minn<<endl;

}