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

문제

---

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

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

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

 

입력

---

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

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

출력

---

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

 

문제 풀이

---

평범한 배낭 문제.

2차원 dp 배열을 선언한 후, i번째 과목까지에 대해 j시간에 얻을 수 있는 최대 중요도를 구한다. j가 i번째 과목에 필요한 공부 시간보다 작으면, i번째 과목을 공부할 수 없으므로, dp[i][j]는 i-1번째 과목까지에 대해 j 시간에 얻을 수 있는 최대 중요도가 된다. 즉, dp[i][j]=dp[i-1][j]이다.

 

j가 i번째 과목에 필요한 공부 시간보다 크거나 같으면, i번째 과목을 공부할 수도 있고, i번째 과목을 공부하지 않을 수도 있다. 만약 i번째 과목을 공부한다면, i-1번째 과목까지에 대해 j - (i번째 과목의 필요 공부 시간) 만큼 중요도를 얻은 후, i번째 과목의 필요 공부 시간만큼의 중요도를 얻으면 된다. i번째 과목의 필요 공부 시간을 studyTime, 중요도를 importance라 한다면, dp[i][j] = dp[i-1][j-studyTime] + importance가 된다.

i번째 과목에 대해 공부하지 않으면, i-1번째 과목까지에 대해 j 시간에 얻을 수 있는 최대 중요도가 dp[i][j]가 된다.

 

dp 배열을 채운 후, dp[K][N]을 출력해주면 된다.

 

아래는 코드.

#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, K;
	cin >> N>>K;
	pair<int, int>* subjects = new pair<int, int>[K];
	long long** dp = new long long*[K+1];
	for (int i = 0; i < K+1; i++)
	{
		dp[i] = new long long[N + 1];
		for (int j = 0; j < N + 1; j++)
		{
			dp[i][j] = 0;
		}
	}
	for (int i = 0; i < K; i++)
	{
		cin >> subjects[i].second >> subjects[i].first;
	}
	sort(subjects, subjects + K);
	for (int i = 0; i < K; i++)
	{
		int studyTime = subjects[i].first;
		int importance = subjects[i].second;
		for (int j = 0; j < N+1; j++)
		{
			if (j < studyTime)
			{
				dp[i + 1][j] = dp[i][j];
			}
			else
			{
				dp[i + 1][j] = max(dp[i][j - studyTime] + importance, dp[i][j]);
			}
		}
	}
	cout << dp[K][N] << "\n";
	return 0;
}