백준 15459 : Haybale Feast

문제 링크

각 음식마다 f와 s가 주어지고, 여러개 음식의 맛는 f들의 합, 매운정도는 s중 최댓값이라고 할 때, 연속된 음식을 선택해서 맛이 m을 넘는 경우 중 가장 매운정도가 적게 되는 경우를 선택하는 문제이다.

이분탐색을 통해 해결하였다.

길이가 n인 배열에서, 음식들을 매운맛이 k이하가 되도록 연속되게 선택하여 그 중 가장 맛이 높은 경우를 찾는 것은 O(n)만에 가능하다. 따라서 이분탐색을 통해 매운맛이 가장 낮은 경우에 대해서 판단하면 된다.

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

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,ll> pll;

ll n,m;
vector<pll> hay;

ll maxflavor(int k)
{
    ll ret = 0;

    ll temp = 0;
    for(int i = 0;i<n;i++)
    {
        if(hay[i].second <= k)
        {
            temp += hay[i].first;
            ret = max(temp,ret);
        }
        else
        {
            temp = 0;
        }
    }

    return ret;
}

int bisearch(int s,int e)
{
    if(s >= e) return e;

    int mid =(s+e)/2;

    if(maxflavor(mid) >= m) return bisearch(s,mid);
    else return bisearch(mid+1,e);
}

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

    for(int i = 0;i<n;i++)
    {
        int f,s;
        scanf("%d %d",&f,&s);

        hay.push_back({f,s});
    }

    printf("%d",bisearch(0,1e9));
    return 0;
}