백준 17845(수강 과목)

www.acmicpc.net/problem/17845

17845번: 수강 과목

xkdlaldfjtnl.tistory.com/122?category=903992

위 4190이랑 같은 문제이다. 

 

 

정해진 범위가 있고, 하나하나 추가하면서 dp에 저장하는 문제. 

 

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
#define MAX 1005

int N, K;
int dp[100001];
vector<pair<int, int> > sub;

int main() {
	cin >> N >> K;
	for (int i = 0; i < K; i++) {
		int a, b;
		cin >> a >> b;
		sub.push_back(make_pair(a, b));
	}
	for (int i = 0; i < K; i++) {
		pair<int, int> p = sub[i];
		for (int j = 10000; j >= 0; j--) {
			if (dp[j] && j + p.second <= 10000) {
				dp[j + p.second] = max(dp[j + p.second], dp[j] + p.first);
			}

		}
		if (dp[p.second] <p.first)dp[p.second] = p.first;
	}
	int ans = -1;
	for (int i = 0; i <= N; i++) {
		if (ans < dp[i])ans = dp[i];
	}
	cout << ans;
}