[알고리즘] 퇴사

구현 방식

• 현재 날짜에서 일했을 때 현재 날짜까지 얻을 수 있는 최대 이익을 배열 acc에 담는다고 할때 아래와 같은 점화식을 얻을 수 있다.

# 0 <= i < k , i + t[i] 는 k 이하이어야함. 
acc[k] = max(p[k]+ acc[i] , acc[k])

• 그러면 acc 에 차곡차곡 쌓인 값중에서, 해당업무를 수행했을 때 N 이하의 날짜로 끝날 수 있는 일중 최대 값을 가지는 날짜의 값을 출력한다.

코드

• 최종 코드는 아래와 같다.

int times[16] = {};
int prices[16] = {};
vector<int> acc(16, 0);

int dp(int N)
{
    for (int curr = 1; curr < N; curr++)
    {

        for (int prev = 0; prev < curr; prev++)
        {
            if (times[prev] + prev <= curr)
            {
                acc[curr] = max(prices[curr] + acc[prev], acc[curr]);
            }
        }
    }

    int result = 0;
    for (int day = 0; day < N; day++)
    {
        if (day + times[day] <= N)
            result = max(result, acc[day]);
    }

    return result;
}