백준 1106 - 호텔 (C++)

 

 

도시별로 홍보 비용과 기대 효과가 주어진다.

 

A도시에서 5원을 사용하면, 3명의 고객이 확보된다는 정보가 있고

B도시에서 3원을 사용하면, 1명의 고객이 확보된다는 정보가 있다고 해보자. (정보는 확실하다고 가정한다.)

 

같은 도시의 홍보를 여러 번 할 수 있기 때문에, A도시에서 10원을 사용한다면 6명의 고객을 확보할 수 있다.

 

이 때, 내가 12명의 고객을 늘리고 싶다면, 어떻게 홍보를 선택해야 최소 비용으로 12명 이상의 고객을 늘릴 수 있을까?

 

문제 풀이

다이나믹 프로그래밍을 활용하면, 문제를 해결할 수 있다.

DP배열을 만든 뒤, i번 인덱스에 대해 i원을 사용했을 때 확보할 수 있는 고객의 최대 수를 저장할 것이다.

 

이 때, 내가 모으고 싶은 고객의 수가 12명이라고 한다면 DP배열에서 가장 먼저 12 이상의 수가 나오는 인덱스를 답으로 반환하면 된다.

 

12 2
3 5
1 1

 

위의 입력에 대해 과정을 알아보자.

위의 표는 DP 배열이다. 인덱스는 사용할 가격이며, 원소의 값은 해당 가격을 사용했을 때 확보할 수 있는 고객의 최대 수이다.

 

먼저, 첫번째 입력인 3, 5에 대해 갱신을 해보자.

 

가격은 최소가 3원 단위이기 때문에, (3, 5)의 홍보를 이용해선 1원과 2원을 사용해서는 고객을 확보할 수 없다.

즉, 1원과 2원에 대해서는 위와 같이 갱신될 것이다.

 

다음 3원에 대해서 갱신해보자. 3원의 경우엔 5명의 고객을 확보할 수 있을 것이다.

4원과 5원을 사용하더라도, 역시나 3원 단위로밖에 돈을 사용할 수 없으므로 3원을 사용했을 때와 동일하게 5명을 확보할 수 있다.

위의 표와 같이 값을 갱신할 수 있다.

동일하게 반복하면 표는 아래와 같아진다.

(3, 5)의 광고에 대해서는 이렇게 갱신할 수 있다.

 

이제 다음 입력인 (1, 1)의 광고를 기준으로 배열의 값을 한 번 더 갱신해보자.

먼저, 1원과 2원에 대해서는 기존에 0이었던 값을 1과 2로 갱신할 수 있다.

이번 광고는 가격이 1원단위이기 때문이다.

 

그런데, 3원을 보자. 현재 광고를 기준으로 하면 3원을 사용했을 때 3명밖에 확보하지 못한다.

하지만, DP배열에 저장된 값은 5이다. 그러므로 3원에 대해서는 갱신할 수 없다.

3원에 대해서는 가격이 갱신되지 않고 고정될 것이다.

반면, 4원 5원을 보자.

 

4원의 경우, 3원으로 5명을 확보한 뒤 1원으로 1명을 더 확보할 수 있다.

5원의 경우에도, 3원으로 5명을 확보한 뒤 2원으로 2명을 더 확보할 수 있다.

 

현재 광고의 가격을 Cost, 확보할 수 있는 고객의 수를 man이라고 한다면 

D(N) = D(N - Cost) + Man 이라는 점화식을 세울 수 있다.

 

현재 광고를 사용한다고 가정했을 때 최대값은 당연히 광고 가격을 뺀 가격에서 최대한으로 확보할 수 있는 고객의 수에 현재 광고를 통해 확보할 수 있는 고객의 수를 더하는 것이 최대 기대값일 것이다.

 

하지만, 그 값이 기존 값보다 항상 크다고 할 수는 없으므로 D(N) = std::max(D(N), D(N - Cost) + Man)이 된다.

 

이 점화식을 통해 배열을 갱신하면, 아래와 같이 갱신된다.

즉, 12명을 확보하기 위해서 최소값은 12 이상의 값이 처음으로 나오는 인덱스의 값인 8이 된다.

 

코드 풀이

int TargetValue = 0;
int NumCity = 0;

std::cin >> TargetValue >> NumCity;

std::vector<std::pair<int, int>> ADs(NumCity);
for (int i = 0; i < NumCity; i++)
{
    std::cin >> ADs[i].first;
    std::cin >> ADs[i].second;
}

먼저, 입력을 모두 저장해준다.

std::vector<int> DP(100001);
for (int i = 0; i < NumCity; i++)
{
    for (int j = 1; j <= 100000; j++)
    {
        int Cost = ADs[i].first;
        int Mans = ADs[i].second;

        if (j - Cost >= 0)
        {
            DP[j] = std::max(DP[j], DP[j - Cost] + Mans);
        }
    }
}

위에서 말했던 점화식 그대로 계속 배열을 갱신해주면 된다.

모든 광고에 대해 갱신을 계속하였다.

 

여기서, DP을 왜 100001로 resize하였나 의문이 들 수 있다.

입력조건 범위를 보면, 확보하고 싶은 고객의 최대 수는 1000명이고, 광고의 최대 비용은 100원이다.

 

이 조건으로 인해, 100원을 들여서 1명을 확보하는 경우가 가장 비싼 경우일 것이다.

이 경우에 1000명을 확보하기 위해선, 10만원이 필요하기 때문에 DP를 가능한 최대 가격인 100000으로 갱신해주었다.
(100000 + 1 인 이유는 인덱스를 직관적으로 사용하기 위해)

 

물론, 입력받은 값을 기준으로 1인당 비용의 최대값을 구한 뒤, 그 값을 기준으로 DP를 갱신할 수도 있지만 실제로 프로그램을 만드는 것이 아니니 이런 사소한 부분은 넘어가고 최대한 편하게 구현하는 것이 좋다고 생각한다.

 

int Answer = std::lower_bound(DP.begin(), DP.end(), TargetValue) - DP.begin();
std::cout << Answer;

return 0;

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

 

lower_bound는 해당 값보다 크거나 같은 원소 중 가장 앞에 있는 원소의 이터레이터를 반환해준다.

이터레이터의 포인터 연산으로 인해, Lower_bound가 반환해주는 값 - begin을 하면 해당 원소의 인덱스를 구할 수 있다.

 

그렇게 구한 인덱스를 답으로 출력해주면 된다.

 

코드 전문

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

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

int main()
{
    Init();

    int TargetValue = 0;
    int NumCity = 0;

    std::cin >> TargetValue >> NumCity;

    std::vector<std::pair<int, int>> ADs(NumCity);
    for (int i = 0; i < NumCity; i++)
    {
        std::cin >> ADs[i].first;
        std::cin >> ADs[i].second;
    }

    std::vector<int> DP(100001);
    for (int i = 0; i < NumCity; i++)
    {
        for (int j = 1; j <= 100000; j++)
        {
            int Cost = ADs[i].first;
            int Mans = ADs[i].second;

            if (j - Cost >= 0)
            {
                DP[j] = std::max(DP[j], DP[j - Cost] + Mans);
            }
        }
    }

    int Answer = std::lower_bound(DP.begin(), DP.end(), TargetValue) - DP.begin();
    std::cout << Answer;

    return 0;
}