[Baekjoon,14501]퇴사

해결

모든 상담에서 적절히 선택해 최고의 조합을 찾아내는 문제이다. 오늘이 day일 일때 day일차의 상담을 하느냐 안하느냐로 선택해 나가면 된다. 단순히 모든 방법의 수를 고려하여 코드를 작성할 수도 있다. 하지만 더욱 효율적인 방법이 있다.

중복되는 부분을 저장하자

현재 N일까지의 상담에서 선택을 해야 하는데 이미 N-1일차때 어떤 선택을 해야 최고 값을 얻는지 안다면 다시 중복하여 이 부분을 계산할 필요는 없다. 즉 중복되는 day일차의 계산을 cache배열에 저장하여 이미 계산된 경우 이 값을 활용하면 불필요한 중복 계산을 방지하여 속도를 향상 시킬 수 있다. 하지만 메모리는 더 차지할 수 밖에 없다.

주의사항

7일차 내에서 선택해야 하는데 6일차 상담이 4일이 걸린다면 끝낼 수 있는가? 당연히 끝낼 수 없다. 이런 경우는 해당 상담의 이익을 음의 무한대로 저장하면 쉽게 처리할 수 있다.

구현

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAX=16;
const int NEG_INF=-987654321;

int N,cache[MAX];
vector<pair<int,int> > plan;

int solve(int day)
{
    // 기저 사례
    if(day>N)
        return 0;
    
    int& ret=cache[day];
    if(ret!=-1)
        return ret;
    // day일의 상담을 하는 것과 안하는 것 중 큰 값 반환
    return ret=max(plan[day].second+solve(day+plan[day].first) ,solve(day+1));
}

int main()
{
    cin>>N;
    // 요구 기간, 이익
    plan=vector<pair<int,int> >(N);
    // 1일차 부터 차례로 저장
    for(int i=1;i<=N;++i)
    {
        cin>>plan[i].first>>plan[i].second;
        // 남은 상담 일수를 다 못채우는 경우
        if(plan[i].first>N-i+1)
            plan[i].second=NEG_INF;
    }
    memset(cache,-1,sizeof(cache));
    
    // 1일차 부터 차례로 선택 결정
    cout<<solve(1)<<endl;
    
    return 0;
}