[C/C++] 백준 - 1106번 : 호텔

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

1106번: 호텔

문제

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

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

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

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

 

 

C명의 호텔 고객을 유치하기 위해 투자해야하는 최소 금액을 구해야하는 문제이다.

얼마를 투자해서 몇 명을 유치할 수 있는 정보가 주어지기에 나에게 주어지는 선택은 2가지이다.

 

그 금액을 지불하여 고객을 유치할지 / 그 금액을 지불하지 않고 고객을 유치 안할지

즉, 이 문제는 0/1 배낭 문제와 같은 동적계획법으로 해결이 가능하다.

 

나는 늘 하던 방식으로 재귀 함수 방식으로 구현하였다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#include <ctime>
#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define ENDL cout << endl
#define ll long long
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000007
#define endl '\n'

using namespace std;

int C, N, answer = INF;
int cost[22];
int returnValue[22];
int cache[2500][30];

void input() {
	cin >> C >> N;
	memset(cache, -1, sizeof(cache));
	for (int i = 0; i < N; i++) {
		cin >> cost[i] >> returnValue[i];
	}
}

int solution(int customer, int index) {
	if (index < 0) {
		if (customer <= 0) return 0;
		else return INF;
	}
	if (customer <= 0) {
		return 0;
	}

	int& ret = cache[customer][index];
	if (ret != -1) return ret;
	ret = solution(customer, index-1);
	if (customer > 0) ret = min(ret, solution(customer - returnValue[index], index) + cost[index]);
	return ret;

}

int main() {
	fastio;
	input();
	cout << solution(C, N) << endl;

	return 0;
}