[C++] 최대점수 구하기(냅색 알고리즘) 🔥

📄문제

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)

 

⬇️ 입력

첫 번째 줄에 문제의 개수N(1<=N<=100)과 제한 시간 M(10<=M<=1000)이 주어집니다.
두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.

5 20 10 5 25 12 15 8 6 3 7 4

 

⬆️ 출력

첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.

41

 

📝 풀이

#include <iostream>
using namespace std;

int dp[1001];

int main()
{
	ios_base::sync_with_stdio(false);

	int N, M, res = INT_MIN;
	cin >> N >> M;

	for (int i = 0; i < N; ++i)
	{
		int t;
		int s;
		cin >> s >> t;

		// 각 문제당 한번씩만 푼다는 조건이 있기때문에
		// for문을 M부터 t까지 역으로 돌아 현재 score에 대한 중복 적용이 없도록 구현
		for (int j = M; j >= t; --j)
		{
			dp[j] = max(dp[j], dp[j - t] + s);
			res = max(res, dp[j]);
		}
	}

	cout << res;
}

• 냅색 알고리즘을 적용하되, 이번 문제는 반복문을 마지막부터 시작해야합니다.
• 풀어야 할 문제가 중복으로 풀 수 없고, 하나만 풀 수 있기에 t 인덱스부터 끝까지 접근하면 t마다 점수가 배수로 저장이 됩니다. (보석문제)