[BOJ/Gold 5] 백준 17845 수강 과목(C++)

문제 링크

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

17845번: 수강 과목

 

문제

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

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

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

입력

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

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

출력

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

예제 입력 1

80 3
650 40
700 60
60 40

예제 출력 1

710

알고리즘 분류

• 배낭 문제

풀이

특정 과목을 선택했을 때 공부 시간이 얼마일 때의 중요도를 기록하기 위하여 DP[1000][10000]라는 2차원 배열을 선언한다. 이것은 i번째 과목까지 탐색했을 때 공부 시간이 j일 때의 중요도를 일컫는다. 과목은 K개이고, K는 최대 1,000까지 되며, 공부 시간은 N이고, N은 최대 10,000까지 되므로 1000X10000 크기의 2차원 배열로 선언해주었다.

다음으로는 K개의 과목을 첫 번째 과목부터 탐색하면서, 이 과목을 선택했을 때 공부 시간이 j가 될 때의 중요도와 이 과목을 선택하지 않았을 때의 공부 시간이 j가 될 때의 중요도를 비교하여 더 큰 값을 기록한다. 그와 동시에 중요도의 최댓값을 계속 구해준다.

마지막으로 미리 구해둔 중요도의 최댓값을 출력해주면 된다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX_I 100001
#define MAX_T 10001
#define MAX_K 1001
#define LL long long
#define INF 1e9

using namespace std;
int N, K;
LL I[MAX_I], T[MAX_T];
LL DP[MAX_K][MAX_T];
LL Answer = 0;

void Input() {
	cin >> N >> K;
	for (int i = 1; i <= K; i++) {
		cin >> I[i] >> T[i];
	}
}

void Settings() {
	for (int i = 1; i <= K; i++) {
		for (int j = 1; j <= N; j++) {
			if (j - T[i] >= 0) {
				DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - T[i]] + I[i]);
			}
			else {
				DP[i][j] = DP[i - 1][j];
			}
			Answer = max(Answer, DP[i][j]);
		}
	}
}

void Find_Answer() {
	cout << Answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}