[백준] 1106 호텔

 

문제

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

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

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

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

입력

첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

냅색 문제입니다.

1~K원까지 N번째 도시를 홍보하면서 유치할 수 있는 고객의 수를 갱신해갑니다.

다만 이때 K원, 즉 몇원까지 설정하는지가 중요한데,,,,, (메모리,시간초과)

각 도시의 홍보비용과 고객의 수는 최대 100이고, 최대 1000명의 고객을 유치해야하므로,

K, 즉 배열의 크기는 100000으로 잡으면 됩니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)
#define all(v) v.begin(), v.end()
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 100001;

int C, N, a[100001], c, n;
int main() {
	FAST;
	cin >> C >> N;
	while (N--) {
		cin >> c >> n;
		for (int i = c; i <= INF; i++) {
			a[i] = max(a[i], a[i - c] + n);
			if (a[i] >= C) {
				INF = i;
				break;
			}
		}
	}
	cout << INF;
}