[BOJ / C++] 1106번 : 호텔

문제

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

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

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

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

입력

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

출력

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

Solved.ac 레벨

골드 V

풀이

dp 문제였다. 카테고리를 보니 배낭 문제도 있었다. 지난 번에 푼 기본적인 배낭 문제가 재밌어서 또 연습해볼까 했는데...

조금 더 알아보니 배낭 문제에도 종류가 있는 모양이다.

 

1차원 dp 배열을 사용했다. dp[i]의 값은 i원을 투자했을 때 늘릴 수 있는 최대 고객 수를 나타내고, i의 범위는 100,001까지이다.

늘려야 하는 고객 수, C의 범위가 C <= 1,000. 도시 홍보비용과 고객의 수 범위 <= 100. 이 둘의 곱 + 1이 최대범위가 된다.

 

예제를 활용하여 문제를 푸는 과정을 나타내보자.

 

늘려야 하는 최소 고객 수 c = 12

도시의 개수 n = 2

 

2개의 도시에서 비용 대비 인원은 다음과 같다.

pair<int, int> 타입의 vector, v로 저장하여 사용할 것이다.

비용 (first)	3	1
고객 (second)	5	1

 

dp 배열의 변화를 나타낸 표를 통해 1원부터 늘릴 수 있는 최대 고객 수를 구해보자.

dp 배열은 초기에 0으로 초기화를 해두었다.

 

1. 1원으로 고객을 늘릴 경우

금액	1원	2원	3원	4원	5원	6원	7원	8원
최대 고객 수	1	0	0	0	0	0	0	0

v를 순회하며 각 비용 대비 늘릴 수 있는 고객의 수를 확인한다. 문제에서는 정수배를 활용하였지만 앞서 말했듯 나는 이 조건을 확인하지 못했다...

나는 i원 - 현재 v의 금액 + 현재 v의 인원으로 접근해보았다.

 

1. v[0] 3원으로 5명

현재 1원으로 늘릴 수 있는 고객의 수 dp[1] = 0과 dp[1 - 3] + 5를 비교한다.

dp[-2]는 존재하지 않고, 최대 고객의 수는 여전히 0이다.

 

2. v[1] 1원으로 1명

현재 1원으로 늘릴 수 있는 고객의 수 dp[1] = 0과 dp[1 - 1] + 1를 비교한다.

dp[0]은 0으로 초기화되어 있기 때문에 dp[0] + 1은 1, 최댓값은 1이 되며 dp[1]은 1로 대체된다.

 

2. 2원으로 고객을 늘릴 경우

금액	1원	2원	3원	4원	5원	6원	7원	8원
최대 고객 수	1	2	0	0	0	0	0	0

1. v[0] 3원으로 5명

현재 2원으로 늘릴 수 있는 고객의 수 dp[2] = 0과 dp[2 - 3] + 5를 비교한다.

여전히 비교 대상이 dp 배열의 음수 인덱스이므로 존재하지 않고, 최대 고객 수는 여전히 0이다.

 

2. v[1] 1원으로 1명

현재 2원으로 늘릴 수 있는 고객의 수 dp[2] = 0과 dp[2 - 1] + 1를 비교한다.

dp[1] = 1이고 dp[1] + 1 = 2, 비교했을 때 최댓값은 2가 되며 dp[2]는 2로 대체된다.

 

3. 3원으로 고객을 늘릴 경우

금액	1원	2원	3원	4원	5원	6원	7원	8원
최대 고객 수	1	2	5	0	0	0	0	0

1. v[0] 3원으로 5명

현재 3원으로 늘릴 수 있는 고객의 수 dp[3] = 0과 dp[3 - 3] + 5를 비교한다.

dp[0] = 0이고 dp[0] + 5 = 5, 0과 비교했을 때 최댓값은 5가 되며 dp[3]은 5로 대체된다.

 

2. v[1] 1원으로 1명

현재 3원으로 늘릴 수 있는 고객의 수 dp[3] = 5과 dp[3 - 1] + 1를 비교한다.

dp[2] = 2이고 dp[2] + 1 = 3, 비교했을 때 최댓값은 5가 되며 dp[2]는 5로 유지된다.

 

(중략)

 

위와 같은 과정을 거쳐 8원까지 값을 채운다.

금액	1원	2원	3원	4원	5원	6원	7원	8원
최대 고객 수	1	2	5	6	7	10	11	12

8원을 이용해 최대 고객 수의 값이 12, c와 같아졌다.

문제에서 최소 c명의 고객을 모은다고 했으므로 c명인 12명이 모아진 시점의 금액, 8을 출력한다.

 

위 과정을 통해 도출된 점화식은 아래와 같다.

dp[i] = max(dp[i], dp[i - v[j].first] + v[j].second)

Code

#include<bits/stdc++.h>
#define MAX 100001

using namespace std;

int c, n;
int dp[MAX];
vector <pair<int, int>> v;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> c >> n;

    for(int i = 1; i <= n; i++) {
        int cost, people;
        cin >> cost >> people;
        v.push_back({cost, people});
    }

    for(int i = 1; i <= MAX; i++) {
        for(int j = 0; j < n; j++) {
            if(i - v[j].first >= 0) {
                dp[i] = max(dp[i], dp[i - v[j].first] + v[j].second);
            }
        }
        if(c <= dp[i]) {
            cout << i << "\n";
            break;
        }
    }


    return 0;
}

1106번: 호텔