[BOJ] 7579 앱

나는 사용가능한 최대 cost를 정해두고 0/1 knapsack을 돌리는걸 파라메트릭 서치로 해서 AC를 받았는데 보니까 아무도 이렇게 풀지 않았다 ㅠㅠ 억울해서 소스를 올린다.

#include <bits/stdc++.h>
 
using namespace std;
 
int n,m;
int arr[105];
int cost[105];
int cache[105][10005];
 
int dp(int idx, int remain)
{
    if(idx==(n+1)) return 0;
    int& ret=cache[idx][remain];
    if(ret!=-1) return ret;
 
    int ma=dp(idx+1,remain);
    if(remain>=cost[idx]) ma=max(ma,dp(idx+1,remain-cost[idx])+arr[idx]);
    return ret=ma;
}
 
bool isAvail(int goal)
{
    memset(cache,-1,sizeof(cache));
    if(dp(1,goal)>=m) return true;
    else return false;
}
 
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&arr[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&cost[i]);
    int le=0,ri=10000,mid,ans=10000;
    while(le<=ri)
    {
        int mid=(le+ri)>>1;
        if(isAvail(mid))
        {
            ans=min(ans,mid);
            ri=mid-1;
        }
        else
            le=mid+1;
    }
    printf("%d",ans);
    return 0;
}