[알고리즘 문제] 백준14501 - 퇴사

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

14501번: 퇴사

개인적으로 이 문제의 핵심은 재귀함수의 for문에서 반복을 시작하는 시점이다. 3일걸리는 일을 선택했다면 현재~3일 사이의 일은 선택할 수 없다. 이 부분을 잘 처리해줘야 한다.

 

아래의 코드에서 for문의 반복시작점은 day인데, 이는 곧 info의 index값이 된다. 그리고 다음 재귀함수를 돌릴 때 day값에 i + 선택한 작업이 걸린 일수를 넣어줌으로써 일을 처리하는 동안 그사이에 존재하는 다른 일을 선택하지 못하도록 하였다.

 

처음에 visited배열을 선언해서 선택한 일들에 대한 중복처리를 하였는데 이런 식으로 반복문의 시작점은 day로 해주면 그렇게 해줄 필요도 없다. 

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

using namespace std;

int N, T, P, answer = -1;
vector<pair<int, int>> info;

void search(int day, int cost)
{
    if (day > N)
    {
        return;
    }
    answer = max(answer, cost);

    for (int i = day; i < info.size(); i++)
    {
        search(i + info[i].first, cost + info[i].second);
    }
}

int main()
{
    cin >> N;
    int a, b; // 날짜, 비용

    for (int i = 0; i < N; i++)
    {
        cin >> a >> b;
        info.push_back(make_pair(a, b));
    }
    search(0, 0);
    cout << answer;
    return 0;
}