백준 15486 - 퇴사 2 (C++)

 

 

백준이가 퇴사하기 전까지 N일동안 최대의 이익을 얻는 것이 목표이다.

각 날짜별로 상담이 잡혀있으며, 각 상담별로 상이하게 소요 시간과 상담료가 설정되어있다.

이 때, 최고 효율로 상담을 선택하여 총 이익을 최대값을 구하면 된다.

 

문제 풀이

본인은 다이나믹 프로그래밍을 활용하여 문제를 해결하였다.

 

DP배열을 만들어서, 각 인덱스에는 인덱스에 해당하는 날짜까지 얻을 수 있는 총 이익의 최대값을 저장할 것이다.

이 때, 가장 기본적으로 성립하는 것은 당연히 DP[i] >= DP[i - 1]이라는 것이다.

 

3일동안 벌 수 있는 총 이익이 2일동안 벌 수 있는 총 이익과 같을 수는 있어도 더 적을 수는 없기 때문이다.

 

그러므로, DP[i] = std::max(DP[i], DP[i - 1])의 점화식이 먼저 성립하게 된다.

 

만약, 6일부터 10일까지 상담을 진행함으로써 7일 8일 9일 10일엔 상담을 새로 받을 수 없으므로 7~10일의 값은 DP[6]의 값을 그대로 가져갈 것이다.

 

DP[i] = std::max(DP[i], DP[i - 1])이라는 점화식은 특정 날짜에 상담을 새로 배정할 수 없다면, 현재 맡고 있는 상담의 시작날짜의 값을 그대로 가져가겠다는 의미로 해석할 수도 있다. (DP배열의 초기값은 0이기 때문에)

 

그리고, 한가지 점화식을 더 만들어야 한다.

 

i일에 시작해서 n일이 걸리는 상담을 맡았다고 해보자.

그렇다면, 해당 상담의 종료 일자는 (i + n - 1)일이 될 것이다.

((i + n - 1)일까지 상담이므로, (i + n - 1)의 상담을 맡을 수는 없음)

 

해당 상담의 상담료가 p원이라고 한다면, (i + n - 1)에는 p원의 이익이 추가될 것이다.

즉 DP[i + n - 1] = DP[i  - 1] + p; 라고 할 수 있다.

(i일 전까지 얻었던 총 이익 + i일에 시작하는 상담의 상담료)

 

하지만, 다른 날짜에서 (i + n - 1)과 동일한 날에 종료하는 상담을 계산함으로써 DP[i + n - 1]이 이미 0이 아닌 값으로 갱신되어 있을 수도 있다.

 

예를 들면, 3일에 시작해서 2일이 걸리는 상담도 5일에 끝이나며 1일에 시작해서 5일이 걸리는 상담도 5일에 끝이난다.

이런 경우엔 두 상담의 이익을 비교해서 더 큰 쪽으로 값을 갱신해주어야 한다.

 

그러므로 DP[i + n - 1] = std::max(DP[i + n - 1], DP[i - 1] + p); 라는 점화식을 세울 수 있다.

 

1일차부터 퇴사하는 날까지 모든 날에 대해 위의 두개의 점화식으로 DP배열을 갱신하게 되면, DP배열의 마지막 원소가 정답이 된다.

 

코드 풀이

int Days = 0;
std::cin >> Days;

std::vector<std::pair<int, int>> Task(Days + 1);
for (int i = 1; i <= Days; i++)
{
    std::cin >> Task[i].first;
    std::cin >> Task[i].second;
}

먼저, 모든 입력을 받아서 저장해주었다.

std::vector<int> DP(Days + 1);
for (int i = 1; i <= Days; i++)
{
    int EndDay = Task[i].first + i - 1;

    if (EndDay <= Days)
    {
        DP[EndDay] = std::max(DP[EndDay], DP[i - 1] + Task[i].second);
    }

    DP[i] = std::max(DP[i], DP[i - 1]);
}

다음은 위에서 말했던 것과 같이 DP배열을 갱신해주었다.

 

std::cout << DP[Days];

return 0;

마지막으로 출력해주면 된다.

 

 

DP문제는 코드가 길거나 구현하기 까다로운 경우는 많지 않다.

대부분 아이디어를 구상하는 것이 어렵기 때문에, 문제를 자주 풀어보고 생각해보는 것이 중요한 것 같다.

 

코드 전문

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

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();
    
    int Days = 0;
    std::cin >> Days;

    std::vector<std::pair<int, int>> Task(Days + 1);
    for (int i = 1; i <= Days; i++)
    {
        std::cin >> Task[i].first;
        std::cin >> Task[i].second;
    }
    
    std::vector<int> DP(Days + 1);
    for (int i = 1; i <= Days; i++)
    {
        int EndDay = Task[i].first + i - 1;

        if (EndDay <= Days)
        {
            DP[EndDay] = std::max(DP[EndDay], DP[i - 1] + Task[i].second);
        }

        DP[i] = std::max(DP[i], DP[i - 1]);
    }

    std::cout << DP[Days];

    return 0;
}