[BOJ/Gold 5] 백준 1106 호텔(C++)

문제 링크

https://www.acmicpc.net/problem/1106

1106번: 호텔

 

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

12 2
3 5
1 1

예제 출력 1

8

예제 입력 2

10 3
3 1
2 2
1 3

예제 출력 2

4

예제 입력 3

10 10
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10

예제 출력 3

10

예제 입력 4

100 6
4 9
9 11
3 4
8 7
1 2
9 8

예제 출력 4

45

알고리즘 분류

• 배낭 문제

풀이

DP[100000]라는 배열을 선언한다. 10만인 이유는, 고객은 최대 1,000명까지 늘릴 수 있고, 도시 홍보 비용은 100이기 때문에 1000 * 100 = 100000이 된다. 이것은 i원을 사용해서 DP[i]명만큼의 호텔의 고객을 늘릴 수 있다는 의미이다.

첫 번째 도시부터, i번째 홍보 비용을 추가로 사용한 비용 j(j는 1부터 100000)를 사용해서 늘릴 수 있는 고객 DP[j]에 i번째 홍보 비용을 추가로 사용해서 늘릴 수 있는 고객의 수를 더해준다.

마지막으로, 1원부터 100,000원까지, i원을 사용해서 적어도 C명의 고객을 늘릴 수 있는 최소의 비용을 찾는다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX_N 21
#define MAX_C 1001
#define LL long long
#define INF 1e9

using namespace std;
int C, N;
int Cost[MAX_N], Client[MAX_N];
int DP[MAX_C * 101];

void Input() {
	cin >> C >> N;
	for (int i = 1; i <= N; i++) {
		cin >> Cost[i] >> Client[i];
	}
}

void Settings() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= 100000; j++) {
			if (j - Cost[i] >= 0) {
				DP[j] = max(DP[j], DP[j - Cost[i]] + Client[i]);
			}
		}
	}
}

void Find_Answer() {
	for (int i = 1; i <= 100000; i++) {
		if (DP[i] >= C) {
			cout << i << "\n";
			break;
		}
	}
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}