[BOJ 14501] 퇴사 (C++)

퇴사(Silver 3)

문제

전체 문제 보기

14501번: 퇴사

접근법

이 문제는 동적 계획법으로 풀 수 있는 문제입니다. 문제에서 주어진 예시는 아래와 같습니다.

백준이가 1일에 상담을 진행하게 되면 3일 뒤인 4일 상담부터 진행할 수 있습니다. 2일에 상담을 진행하게 되면 5일 뒤인 7일부터 다시 상담을 진행할 수 있습니다. 이를 일반화해서 설명하면 다음과 같습니다. 임의의 날 n일에 상담을 진행하게 되면 n + Tn일에 다시 상담을 진행할 수 있는 것입니다. 그리고 어떤 날은 n일에 상담을 하지 않는 것이 더 많은 금액을 얻을 수도 있습니다. 만약 n일에 상담하지 않는다면 다음날인 n+1일의 최대 금액과 동일합니다. 때문에 임의의 날 n에서 금액의 최댓값\(F(n)\)은 다음과 같습니다.

\[F(n) = \mbox{max}(F(n+1), P(n) + F(T(n) + n))\]

단, \(T(n) + n\)이 범위를 배열의 범위를 벗어나지 않도록 예외처리가 필요합니다.

전체 구현

위 점화식을 바텀업 방식으로 다음과 같이 구현할 수 있습니다.

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int main() {

    int N; // N (1 ≤ N ≤ 15)
    scanf("%d ", &N);

    vector<int> cache(N+2);
    vector<int> T(N + 2);
    vector<int> P(N + 2);

    for (int i = 1; i <= N; ++i)
    {
        scanf("%d %d ", &T[i], &P[i]);
    }

    for (int i = N; i >= 1; --i)
    {
        // a: i번째 상담 선택
        // b: i번째 상담 포기
        int a{}, b{};
        // i번째 상담 종료일
        const int end = T[i] + i;
        if(end <= N + 1)
            a = P[i] + cache[end];

        if(i + 1 < N + 1)
            b = cache[i + 1];

        cache[i] = max(a, b);
    }
    printf("%d\n", cache[1]);

    return 0;
}