[BOJ/Gold 4] 백준 33259 상현이의 수강신청 대작전(C++)

문제 링크

https://www.acmicpc.net/problem/33259

 

문제

KSA에서는 자신이 수강하고 싶은 과목을 골라 수강신청을 해야한다. 상현이는 총 학점이 M학점 초과가 되도록 신청하면 도저히 GPA를 유지할 수 없을 것 같아 M학점 이하로 과목들을 골라 신청하고자 한다. 수강신청 가능한 과목은 총 N개이며, 1부터 N까지의 번호가 붙여져 있다. i번 과목에 대한 상현이의 선호도는 Pi이고, 학점은 Ci이다. 이때 총 학점이 M학점 이하면서 선호도의 총합이 최대화되도록 수강신청을 하는 방법을 구하는 프로그램을 작성하시오. (단, 각 과목은 최대 한 번씩만 선택할 수 있으며, 최소 한 과목 이상을 신청해야 한다.)

 

입력

첫 번째 줄에 두 개의 정수 N(1 ≤ N ≤ 5,000)과 M(1 ≤ M ≤ 5,000)이 주어진다.

다음의 N개의 줄 중 i번째 줄에 두 개의 정수 Pi(1 ≤ Pi ≤ 10^5)와 Ci(1 ≤ Ci ≤ 5,000)이 주어진다.

 

출력

첫 번째 줄에 문제의 조건에 따라 수강신청을 하는 방법이 존재한다면 신청할 과목의 수를 출력하고, 아니라면 −1을 출력한다.

만약 그러한 방법이 존재한다면, 두 번째 줄에 신청할 과목의 번호들을 오름차순으로 출력한다.

정답이 여러 개 존재한다면 그중 아무거나 출력해도 상관없다.

 

예제 입력 1

8 13
1 1
9 3
18 2
1 2
13 3
7 3
19 4
15 4

예제 출력 1

4
3 5 7 8

 

이 예제는 상현이의 실제 수강 과목을 반영한 것이다.

예제 입력 2

3 2
3 4
7 3
4 3

예제 출력 2

-1

 

알고리즘 분류

• 배낭 문제

 

풀이

최대 M학점까지 수강 신청을 한 과목의 선호도의 총합이 최대가 되도록 과목들을 담는다.

이후 선호도의 총합이 최대가 되는 학점을 찾고, 이 학점을 기준으로 수강 신청한 과목들을 역추적한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 5001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M;
int P[MAX], C[MAX];
int DP[MAX][MAX];
vector<int> Answers;
int Max_Priority = -1;
int Max_Credit = -1;

void input() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> P[i] >> C[i];
	}
}

void settings() {
	DP[0][0] = 0;

	for (int i = 1; i <= N; i++) {
		for (int j = M; j >= 0; j--) {
			if (j - C[i] >= 0) {
				DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - C[i]] + P[i]);
			}
			else {
				DP[i][j] = DP[i - 1][j];
			}
		}
	}

	for (int i = 0; i <= M; i++) {
		if ((DP[N][i] > 0) && (Max_Priority < DP[N][i])) {
			Max_Priority = DP[N][i];
			Max_Credit = i;
		}
	}

	if (Max_Credit > 0) {
		for (int i = N; i >= 1; i--) {
			if (DP[i][Max_Credit] != DP[i - 1][Max_Credit]) {
				Answers.push_back(i);
				Max_Credit -= C[i];
			}
		}
		sort(Answers.begin(), Answers.end());
	}
}

void printAnswer() {
	if (Answers.empty()) {
		cout << "-1\n";
	}
	else {
		cout << (int)Answers.size() << "\n";
		for (int i = 0; i < (int)Answers.size(); i++) {
			cout << Answers[i] << " ";
		}
		cout << "\n";
	}
}

int main() {
	FASTIO

	input();
	settings();
	printAnswer();

	return 0;
}