전공/알고리즘
백준 17845(수강 과목)
xkdlaldfjtnl
2020. 10. 25. 14:47
17845번: 수강 과목
첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이
www.acmicpc.net
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;
}