앱

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int cache[10000000];
int n, m;
pair<int, int> arr[100];

void func(int sum)
{
//cache: 각 second요소에 달하는데 필요한 메모리의 수
for (int i = 0; i < n; i++)
{
for (int j = sum; j >= arr[i].second ; j--)
{
cache[j] = max(cache[j], 
cache[j - arr[i].second] + arr[i].first);
/*cache[j - arr[i].second]: 현재 가진 돈으로 
살 수 있는 메모리와,
[현재가진돈 - 그간 써온 돈] + 현재 살펴보는 것의
메모리 중 가장 큰 것을 가져감
ex) 15원을 고려: 이전에 15원으로 사둔 것과,
15원-5원, 즉 10원까지 사둔 무언가 + 현재의 5원
으로 살 수 있는 것을 비교
*/
}
}
}

int main()
{
scanf("%d %d", &n, &m);

int temp;
int sum = 0;
for (int i = 0; i < n; i++)
{
scanf("%d", &temp);
arr[i].first = temp;
}
for (int i = 0; i < n; i++)
{
scanf("%d", &temp);
arr[i].second = temp;
sum += temp;
}

func(sum);

int i = 0;
for (i = 0; cache[i] < m; i++)
{

}

printf("%d", i);

return 0;
}