[맞음] 백준 1535 안녕 // 갯수1개 제한 dp

https://www.acmicpc.net/problem/1535

* 풀이

• 갯수제한dp는
• dfs(idx, 상태)로 풀면 되는듯?
• for문으로 할꺼면 뒤에서부터 채우기

#include<bits/stdc++.h>
using namespace std; 

typedef long long ll;

int n;
int hp[24], gi[24];
ll dp[24][104];

ll dfs(int idx, int cnt) {
   if(cnt <= 0 ) {
      return -987654321; //배제
   }
   if(idx==n) {
      return 0;
   }

   ll & ret = dp[idx][cnt];
   if(ret!=-1) {
      return ret;
   }

   ret=0;
   ret=max(ret,dfs(idx+1,cnt)); //선택x
   ret=max(ret,dfs(idx+1,cnt-hp[idx])+gi[idx]); //선택o
   
   return ret;
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);

   memset(dp,-1,sizeof(dp));
   cin>>n;
   for(int i=0;i<n;++i) {
      cin>>hp[i];
   }
   for(int i=0;i<n;++i) {
      cin>>gi[i];
   }
   cout<<dfs(0,100);
}