[백준] 폭탄제조

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

2977번: 폭탄제조

binary search를 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면,

1개의 폭탄을 만들기 위해선, N개의 부품 종류가 필요합니다. N개의 줄에 각 줄마다

 

각각 폭탄 1개에 필요한 부품의 수, 이미 있는 부품의 수, 소형 패키지의 부품수, 소형 패키지의 가격, 대형 패키지에 있는 부품수, 대형 패키지의 가격이 주어질 때, M달러를 이용하여 폭탄을 최대한 만든다면, 몇개 만들수 있는지 구해야 합니다.

 

<Solution>

만들수 있는 폭탄 개수로 이진탐색을 이용해야 합니다. 

 

우선 그러기 위해서 폭탄의 최대와 최소를 구해야 합니다. 폭탄을 0개 만드는 것이 당연히 최소값일 것이고, 최대의 경우 헷갈립니다.

 

저의 경우 만약 가지고 있는 모든 돈으로 첫번째 재료를 최대한 샀을 때 만들수 있는 폭탄의 수(첫번째 재료만 사용한다고 가정)를 최댓값으로 두었습니다. 

    // 첫번째 재료에 대해 최댓값 구하자
    // 작은 패키지 선택 최소, 최대
 
    for(int i = 0; i<=M/Pm[0]; i++){
        // 작은패키지 선택시 자동으로 큰패키지 갯수도 정해짐
        int left_money = M-Pm[0]*i;
        int j = left_money/Pv[0];
 
        // 이 상황에서 해당 재료의 갯수
        int ingredient = i*Sm[0] + j*Sv[0];
        e = max(e, (ingredient+Y[0])/X[0]);
    }

 

다음으로 이제 이 최소와 최대에 대해 이진탐색을 하게 됩니다. 

 

이진 탐색을 하게 되면, 현재 이 갯수의 폭탄을 만들수 있는지 없는지를 판단해주는 is_possible 함수에 대해 생각해 보아야 합니다. 

 

이 함수의 경우, 각 재료를 추가로 사야하는 양을 구해서, 최소의 돈으로 모든 재료를 샀을 때 음수가 되는지 음이 아닌 정수가 되는지를 확인하면 됩니다.

 

실제 구현은 아래와 같습니다. 

#include <iostream>
  
using namespace std;
int N,M;
int X[100+10];
int Y[100+10];
int Sm[100+10];
int Pm[100+10];
int Sv[100+10];
int Pv[100+10];
 
void GET_INPUT(){
    cin >> N >> M;
    for(int i = 0; i<N; i++){
        cin >> X[i] >> Y[i] >> Sm[i] >> Pm[i] >> Sv[i] >> Pv[i];
    }
}
 
bool is_possible(int num_food);
 
int main(){
    // getting input
    GET_INPUT();
 
    // first findout e
    int s = 0;
    int e = 0;
 
    // 첫번째 부품에 대해 최댓값 구하자
    // 작은 패키지 선택 최소, 최대
 
    for(int i = 0; i<=M/Pm[0]; i++){
        // 작은패키지 선택시 자동으로 큰패키지 갯수도 정해짐
        int left_money = M-Pm[0]*i;
        int j = left_money/Pv[0];
 
        // 이 상황에서 해당 부품의 갯수
        int ingredient = i*Sm[0] + j*Sv[0];
        e = max(e, (ingredient+Y[0])/X[0]);
    }
 
    // binary search 
    int sol = -1;
    while(e>= s){
        int mid = (e+s)/2;
        if(is_possible(mid)){
            s = mid+1;
            sol = mid;
        }
        else{
            e = mid-1;
        }
    }
     
    cout << sol << endl;
}
 
bool is_possible(int num_food){
    int cur_money = M;
    for(int i = 0; i<N; i++){
        int money_ = 1<<30;
        // 각 부품의 필요한 양(사야하는)
        int need = X[i]*num_food - Y[i];
 
        // 이 필요한 양을 최소 돈으로 만들어보자.
        // 최소 양을 만들기 위한 작은 패키지 갯수
        int p_range = need/Sm[i];
        if(need%Sm[i] > 0) p_range++;
 
        for(int p = 0; p<=p_range;p++){
            // 이 떄 큰 패키지는 자동결정
            int left_need = need-p*Sm[i];
 
            //큰 패키지수
            int q = (left_need <= 0)? 0 : left_need/Sv[i];
            if(left_need > 0 && left_need%Sv[i] > 0) q++;
 
            money_ = min(money_, p*Pm[i]+q*Pv[i]);
 
        }
 
        // 해당 부품의 최소 돈이 구해졌으므로 뺴자
        cur_money-=money_;
 
        if(cur_money<0) return false;
 
    }
    if(cur_money <0) return false;
    return true;
}