문제 풀이

고객의 수를 최대 1000명 늘이기 위해 투자해야하는 돈의 최소값을 구하기위해 dp의 배열의 인덱스의 최대 값은 홍보당 비용이 최대 100이므로 1000 x 100 = 100,000으로 잡는다.

d[비용] = 해당 비용으로 얻을 수 있는 고객의 최대 수

예제 입력
12 2
3 5
1 1
에서는

노드에는 비용(고객의 수)를 적어놨다.
이렇게 하면 최소한 12명의 고객을 확보하려면 최소 8의 비용이 필요하다는것을 알 수 있다.

문제 링크

boj/1106

소스코드

PS/1106.cpp

#include <iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>

using namespace std;

vector<pair<int, int>> v;
int d[100001];
int main() {
	int c, n;
	cin >> c >> n;
	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		v.push_back({ a,b });
	}
	for (int i = 0; i < v.size(); i++)
	{
			for (int k = 1; k <= 100001; k++)
			{
				if(k- v[i].first >=0)
				d[k] = max(d[k],d[k - v[i].first ] + v[i].second );
			}
		
	}
	for (int i = 1; i <= 100001; i++)
	{
		if (d[i] >= c)
		{
			cout << i;
			break;
		}
	}
}