[백준 1106] 호텔 (C++)

https://www.acmicpc.net/problem/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명 늘리는 것이 아니라 적어도 C명 이상을 늘려야 한다.

예를 들어 6명 이상을 늘려야 하고, 홍보할 수 있는 도시가 1개인데 3원을 들여 4명을 늘릴 수 있다고 한다면, 정확히 6명을 늘리는 것은 불가능하지만 6원을 들여 8명을 늘릴 수 있다. 따라서 dp 배열을 생성할 때 j명 늘릴 때의 최소 비용을 저장하되, 가로 길이는 최대 C까지가 아니라 그 이상을 저장하도록 해야 한다. C-1명일 때까지는 우리가 원하는 답이 아니고, 얻을 수 있는 고객의 수가 최대 100까지이므로 C+99 까지만 생성하면 된다.

 

아래는 코드. 얻을 수 있는 고객의 수를 최대 2000까지 설정해놓았다.

#include <iostream>
#include <utility>
#define MAX 123456789
using namespace std;

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

	int C, N;
	cin >> C >> N;
	int** dp = new int*[N];
	pair<int, int>* cities = new pair<int, int>[N];
	int answer = MAX;
	for (int i = 0; i < N; i++)
	{
		dp[i] = new int[2001];
		cin >> cities[i].first >> cities[i].second;
		for (int j = 0; j < 2001; j++)
		{
			if (j == 0)
			{
				dp[i][j] = 0;
			}
			else
			{
				dp[i][j] = MAX;
			}
		}
	}
	for (int i = cities[0].second; i < 2001; i += cities[0].second)
	{
		int multiple = i / cities[0].second;
		int money = cities[0].first * multiple;
		dp[0][i] = money;
		if (i >= C)
		{
			answer = min(answer, dp[0][i]);
		}
	}
	for (int i = 1; i < N; i++)
	{
		for (int j = 0; j < 2001; j++)
		{
			dp[i][j] = dp[i - 1][j];

			int maxMultiple = j / cities[i].second;
			for (int k = 0; k <= maxMultiple; k++)
			{
				int money = cities[i].first * k;
				int person = cities[i].second * k;
				dp[i][j] = min(dp[i][j], dp[i][j - person] + money);
			}

			if (j >= C)
			{
				answer = min(answer, dp[i][j]);
			}
		}
	}
	std::cout << answer << "\n";
	return 0;
}