백준 1106 호텔 c++ (dp)

문제 출처 : 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보다 작거나 같은 자연수이다.

출력

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

알고리즘 분류

• 다이나믹 프로그래밍

풀이

dp 문제이다.

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

n개의 도시에 최소 비용으로 홍보하여 C만큼의 고객을 만들어야 한다.

dp[i] = 돈을 i 만큼 썼을 때 최대 확보 고객이라 하자.

C는 최대 1000이고, 도시에 홍보할 때 드는 비용은 최대 100이다.

100의 돈을 써서 1명의 고객을 확보할 수 있다고 하면,

dp의 최대 크기는 1000 * 100 +1이 된다.

12 2

3 5

1 1

이 입력으로 주어졌을 때,  

1원을 사용했을 때 최대 고객은 1

2원을 사용했을 때 최대 고객은 2

3원을 사용했을 때 최대 고객은 5

4원을 사용했을 때 최대 고객은 6

5원을 사용했을 때 최대 고객은 7

6원을 사용했을 때 최대 고객은 10

7원을 사용했을 때 최대 고객은 11

8원을 사용했을 때 최대 고객은 12이다.

즉 dp[i]가 3 혹은 1로 나누어진다면 dp[i] = max({dp[i], i/3*5 , i/1*1})로 어떠한 도시의 고객 확보에 들어가는 비용의 정수배 만큼 고객을 홍보했을 때의 값 중 최댓값을 비교하고,

dp[i]= max(dp[i],dp[i-3]+5) 혹은 dp[i] = max(dp[i],dp[i-1]+1)로 이전에 저장해놓은 최댓값에 한 번의 홍보를 더 하는 값 중 최댓값을 비교하면 된다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//1<=C<=1000
//1<=n<=20
int dp[100001];
int answer = 987654321;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int c, n;
	cin >> c >> n;
	vector<pair<int, int>> vt(n);
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		vt[i] = { a,b };
	}

	for (int i = 1; i <= 100000; i++) {
		for (int j = 0; j < n; j++) {
			//나누어 떨어지는 경우
			if (i%vt[j].first == 0) {
				dp[i] = max(dp[i], (i / vt[j].first)*vt[j].second);
			}
			if (i - vt[j].first >= 0) {
				dp[i] = max(dp[i],dp[i-vt[j].first]+ vt[j].second);
			}
		}
		if (c<=dp[i]) {
			cout << i;
			return 0;
		}
	}

	return 0;
}