[BOJ 17845 // C++] 수강 과목

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 17845번 문제인 수강 과목이다.
문제는 아래 링크를 확인하자.

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

17845번: 수강 과목

대표적인 knapsack DP 유형의 문제이다.

 

구체적으로, 과목을 하나씩 추가해 나가면서 각 공부시간마다 채울 수 있는 최대 중요도를 기록해나가는 것으로 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, K;
int arr[10001];

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

	arr[0] = 1;
	cin >> N >> K;
	while (K--) {
		int l, t; cin >> l >> t;
		for (int i = N - t; i > -1; i--) {
			if (arr[i]) {
				if (arr[i + t]) arr[i + t] = max(arr[i] + l, arr[i + t]);
				else arr[i + t] = arr[i] + l;
			}
		}
	}

	int ans = 0;
	for (int i = 0; i <= N; i++) ans = max(ans, arr[i]);

	cout << ans - 1;
}