CodeForces 1282B2(hard version) K for the Price of One

문제 풀이 사고방식 가짜 dp, dp[i]는 전 i개 제품의 비용이 가장 적다는 것을 나타낸다

#include 
#include 
#include 

using namespace std;

const int MAXN = 1e5 + 5;

int price[MAXN], dp[MAXN];

int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		int n, p, k;
		cin >> n >> p >> k;
		for (int i = 1; i <= n; ++i)
		{
			cin >> price[i];
			dp[i] = 0;
		}
		sort(price + 1, price + n + 1);
		for (int i = 1; i <= n; ++i)
		{
			if (i < k)
			{
				dp[i] = dp[i - 1] + price[i];
			}
			else
			{
				dp[i] = min(dp[i - k] + price[i], dp[i - 1] + price[i]);
			}
		}
		int ans = 0;
		for (int i = n; i >= 1; --i)
		{
			if (dp[i] <= p)
			{
				ans = i;
				break;
			}
		}
		cout << ans << endl;
	}
	return 0;
}