백준 Gold 4 호텔

호텔 (백준 Gold 4)

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

호텔 사장이 C명의 고객을 확보하기 위한
홍보 비용 , 예상 고객의 데이터가 N개 주어진다

최소 C명을 확보하기 위한 최소 홍보 비용을 구하는 문제

풀이 방법

기본적으로는 다음과 같이 정립할 수 있음

• dp[i] : i명의 고객을 유치하기 위한 최소 비용
  

• 이전 상태와 비교하여 ‘현재 홍보 계획’을 적용하였을 때의 변화 필요
  

  dp[j] = min(dp[j],dp[j - Clients[i]] + costs[i])
  (더 작은 값으로 대체 가능한지 체크)
  

• 홍보 계획은 ‘배수’ 적용이 가능하므로
  j를 오름차순으로 설정
  

다만,
‘최소 C명’ 이기에
dp[c] 보다 dp[c + n] 같은 경우에
더 ‘낮은 비용’이 존재할 수 있음

• 따라서 c 까지만 ‘딱’ 구하는 것이 아니라
  어느정도 여유를 잡아 구하는 것이 좋음
  (최대 고객 홍보 비용은 약 100 정도이나, 나는 그냥 1000으로 잡았다)
  

제출 코드

#include<iostream>
#include<vector>

using namespace std;

int main()
{
	int c, n;
	cin >> c >> n;

	vector<int> costs, clients;

	for (int i = 0; i < n; i++)
	{
		int c1, c2;
		cin >> c1 >> c2;
		costs.push_back(c1);
		clients.push_back(c2);
	}

	int maxC = c + 1001;

	vector<int> dp(maxC + 1, 1e9);
	dp[0] = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = clients[i]; j <= maxC; j++)
		{
			dp[j] = min(dp[j], dp[j - clients[i]] + costs[i]);
		}
	}

	int ans = 1e9;

	for (int i = c; i <= maxC; i++)
	{
		if (ans > dp[i])
			ans = dp[i];
	}

	cout << ans;

	return 0;
}

결과

dp 로직 자체는 거의 맞았으나
C 범위 탐색에 조금 애를 먹었다