백준 1106 호텔 (c++) : 피너클

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

1106번: 호텔

dp를 이용한 문제다.

cin >> c >> n;
for (int i = 0; i < n; i++) {
	int a, b;
	cin >> a >> b;
	city.push_back({ a, b });
}

c와 n을 입력받은뒤 도시에 홍보했을때 얻는 인워수를 앞에, 홍보할때 드는 비용을 뒤에 둔다.

int solve(int client, int now_city) {
	if (client >= c) return 0;
	if (now_city == n) return 987654321;

함수 solve는 현재 고객수와 현재 도시를 전달받는다.

만약 현재 고객수가 c보다 높다면 0을 리턴한다.

만약 현재 도시가 n이라면, 즉 모든 도시를 돌아볼때까지 고객수가 c를 넘지못했다면 987654321를 리턴한다.

int &ret = cache[client][now_city];
if (ret != -1) return ret;

ret에 cache[client][now_city]를 연결한뒤

-1이 아니라면 ret을 리턴한다.

int ans = 987654321, i = 0;

ans는 답을 입력받을 정수, i는 홍보한 횟수다.

while (client + city[now_city].second * i < c) {
	ans = min(ans, solve(client + city[now_city].second * i, now_city + 1) + city[now_city].first * i);
	i++;
}

현재 고객수와 현재도시에 홍보했을때 얻는 고객의 수가 c보다 작은동안 반복하며

ans와 solve(현재 고객수 + 현재도시에 홍보했을때 얻는 고객의 수, 다음도시) + 홍보한횟수 * 비용을 비교해

더 작은 수를 저장한다. 그후 i++해준다.

ans = min(ans, solve(client + city[now_city].second * i, now_city + 1) + city[now_city].first * i);
return ret = ans;

마지막으로 한번더 해준뒤 ret에 ans를 집어넣으며 리턴한다.

한번더 해주는 이유는 한 도시에서만 홍보해 c를 넘는 경우도 필요하기 때문이다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <cmath>

using namespace std;

int c, n;
int cache[1001][21];
vector<pair<int, int>> city;

int solve(int client, int now_city) {
	if (client >= c) return 0;
	if (now_city == n) return 987654321;

	int &ret = cache[client][now_city];
	if (ret != -1) return ret;

	int ans = 987654321, i = 0;

	while (client + city[now_city].second * i < c) {
		ans = min(ans, solve(client + city[now_city].second * i, now_city + 1) + city[now_city].first * i);
		i++;
	}
	ans = min(ans, solve(client + city[now_city].second * i, now_city + 1) + city[now_city].first * i);
	return ret = ans;
}

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

	memset(cache, -1, sizeof(cache));

	cin >> c >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		city.push_back({ a, b });
	}

	cout << solve(0, 0) << endl;
}

전체코드다.