[백준] 17845번 : 수강 과목 (C++)

17845번 : 수강 과목

---

문제)

유니스트 컴퓨터공학과에 다니는 서윤이는 이번에 어떤 과목을 들을지 고민중이다. 학점을 잘 받을 수 있으면서도 중요한 과목을 듣고 싶은 서윤이는 모든 과목의 중요도와, 일정 이상의 학점을 받기 위해 필요한 공부시간을 다 적었다.

처음에는 모든 과목을 들으려고 했던 서윤이는 자신의 공부 시간에 한계가 있다는 것을 깨달았다. 그래서, 공부 시간의 한계를 초과하지 않으면서 과목의 중요도 합이 최대가 되도록 몇 개만 선택하여 수강하기로 마음먹었다.

중요도가 최대가 되도록 과목을 선택했을 때, 최대가 되는 중요도를 출력하는 프로그램을 작성하시오.

 

 

 

입력 :

첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 

이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 공백을 사이에 두고 주어진다.

 

 

 

출력 :

얻을 수 있는 최대 중요도를 출력한다.

 

 

 

 

풀이)

 

// 17845. 수강 과목
#include <iostream>
#include <vector>
#include <climits>
 
using namespace std;
 
int n, k;
vector<pair<int, int>> vec;
 
int dp[1000][10000];
 
int recur(int cur, int _time)
{
    if (_time > n) return INT_MIN;
    if (cur == k) return 0;
 
    if (dp[cur][_time] != -1)
    {
        return dp[cur][_time];
    }
 
    int ret = 0;
 
    ret = max(recur(cur + 1, _time + vec[cur].second) + vec[cur].first
            , recur(cur + 1, _time));
 
    dp[cur][_time] = ret;
 
    return dp[cur][_time];
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> k;
    vec.resize(k, pair<int, int>());
    for (auto& ele : vec) cin >> ele.first >> ele.second;
 
    fill(&dp[0][0], &dp[999][10000], -1);
 
    cout << recur(0, 0);
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/17845 

17845번: 수강 과목