AlgoSpot) SUSHI

문제 : https://algospot.com/judge/problem/read/SUSHI

주어진 예산에서 최대의 선호도를 찾는 문제입니다.

이때 주어질수 있는 예산의 최대값은  2,147,483,647입니다. 이 수를 이용해서 배열을 만드는게 불가능하므로

슬라이딩 윈도 기법을 이용해서 배열의 수를 줄여야합니다. 

budget 부분의 최대 선호도를 구하기위해서는 budget - 20000 미만의 숫자는 필요가 없습니다.

그리고 물건의 값은 100의 배수이므로 예산과 물건값을 100으로 나눠줍니다.

#include 
#include 
#include 

using namespace std;

int menu[20][2]; //0 은가격 1은 선호도
int cache[201]; // 다음 예산의 값을 정할떄 budget - 20000 이하는 필요가 없고 물건값은 100의 배수이므로 200 + 1(여유)

int n, m; // 초밥의종류 가격

int Max_Pref() {
	int ret = 0;

	cache[0] = 0;

	for (int budget = 1; budget <= m; ++budget) {
		int cand = 0;
		for (int dish = 0; dish < n; ++dish) {
			if (budget >= menu[dish][0]) cand = max(cand, cache[(budget - menu[dish][0]) % 201] + menu[dish][1]);
		}
		cache[budget % 201] = cand;
		ret = max(ret, cand);
	}

	return ret;
}

int main() {
	std:ios::sync_with_stdio(false);
	int C;
	cin >> C;

	while (C--) { // 케이스 시작
		memset(cache, 0, sizeof(cache));
		cin >> n >> m;
		m /= 100;

		for (int i = 0; i < n; i++) {
			cin >> menu[i][0] >> menu[i][1];
			menu[i][0] /= 100;
		}

		cout << Max_Pref() << endl;
	}

	return 0;
}