[백준] 1106

호텔

문제

세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.

형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.

예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.

각 도시에는 무한 명의 잠재적인 고객이 있다. 이때, 호텔의 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

풀이

#include <iostream>
#include <vector>

std::vector<std::pair<int, int> > vec;
int dp[10001];

int main(void) {
    int c, n, u, v, min;

    std::cin >> c >> n;
    for (int i = 0; i < n; i++) {
        std::cin >> u >> v;
        vec.push_back(std::make_pair(u, v));
        dp[v] = std::min(u, dp[v]);
    }

    dp[0] = 0;
    for (int i = 1; i <= 10001; i++) {
        min = 1000000;
        for (int j = 0; j < vec.size(); j++) {
            if (i - vec[j].second < 0) continue;
            min = std::min(dp[i - vec[j].second] + vec[j].first, min);
        }
        dp[i] = min;
    }

    min = 1000000;
    for (int i = c; i < 10001; i++) {
        min = std::min(min, dp[i]);
    }

    std::cout << min;
}

반성회

min 초기값을 100만으로 잡아준 뒤 for 문 내에서 min 값을 변경하는 식으로 풀었다

• vec 벡터의 앞 값 (vec[j].first) 은 금액, 뒷 값 (vec[j].second) 은 홍보되는 사람 수 이므로
• dp[i] 는 dp[i - vec[j].second] + vec[j].first 중 최소값이 된다
  • i - vec[j].second 명에게 홍보하는 데 드는 비용 + vec[j].second 명에게 홍보하는데 드는 비용 (vec[j].first)

문제에서 “적어도 c명 늘이기 위해” 라는 조건이 붙어있어서 정확히 C까지 구하면 틀리고 (예제 2번이 그런 경우)

10000개 정도 구한 다음에 c부터 10001까지의 경우의 수 (dp[c] ~ dp[10001]) 중에서 최소값을 다시 구해주었다