백준 4781 사탕가게 // dp, 갯수무한인경우는 dfs내 for문, 소수처리방법

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

* 시도1

• 사탕선택 o,x로 하면될듯?
• 갯수가 무한대임 -> 불가능

 

* 풀이

• 갯수가무한대인경우 , 상태를 dfs(남은돈) : 그때 최대칼로리로 정의, idx는 제거
• dfs내 for문으로 완탐필요!!
  • for내에서 가능한경우, 노드를 계속생성함!!

• 소수처리방법1
  • scanf로 받아서 각각처리

• 또는 cin으로 받아서 round 처리

 

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

typedef long long ll;

int n;
double m;
vector<pair<int,int>> v; //칼로리, 가격
ll dp[10000+4]; //돈(m) 최대 : 10000원

ll dfs(int money) {
   if(money < 0 ) {
      return -987654321;
   }
   if(money==0) {
      return 0;
   }

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

   ret=0; //리프노드 시작 리턴값
   for(int i=0;i<n;++i) {
      if(money - v[i].second >=0) {
         ret=max(ret,dfs(money-v[i].second) + v[i].first );
      }
   }
   return ret;
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
   
   while(1) {
      cin>>n>>m;
      if(n==0 && m==0.00f) {
         break;
      }
      fill(dp,dp+10004,-1);
      v.clear();
      for(int i = 0; i < n; ++i) {
         int calories;
         double price;
         cin >> calories >> price;
         int price_cents = round(price * 100); // 부동소수점 오차 방지를 위한 반올림
         v.push_back({calories, price_cents});
      }
      cout<<dfs(m*100)<<"\n";
   }
}