[PS] 백준 15732번: 도토리 숨기기

|

문제

내가 이해한 문제 내용

도토리를 담을 수 있는 상자가 있고 각 상자에 담을 수 있는 도토리의 개수에 제한이 없다. 이 때 도토리를 일정 간격으로 담는 규칙이 주어지고 도토리의 개수가 주어질 때 마지막 도토리가 들어가는 상자의 번호를 구하시오.

접근 방식

계속 브루트 포스로 접근하다가 이분탐색을 어느정도 캐치했지만 어떤 방식으로 사용해야 될지가 모르겠어서 힌트를 참고했다. $N$개의 상자를 기준으로 이분탐색을 돌리면서 주어지는 구간에 해당 상자까지 도토리를 몇개 담을 수 있는지 구하면 된다. 그 구한 값을 이용해 주어진 도토리 개수 $D$와 비교하면서 해결한다.

어려웠던 점 & 배운 점

  • 이분탐색의 기준을 잡는 것이 어려웠다.
  • 상자의 범위체크가 까다로워서 여기서 시간을 좀 많이 썼다.

시간복잡도

$O(KlgN)$

코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct box{
    int begin;
    int end;
    int interval;
};

vector<box> boxes;
int n,k,d,a,b,c,l,r,m,mid,ans;
long long num;

int main(void)
{
    scanf("%d%d%d",&n,&k,&d);
    for(int i=0; i<k; i++){
        scanf("%d%d%d",&a,&b,&c);  
        boxes.push_back({a,b,c});
    }

    l=1,r=n,m=2e9;
    while(l<=r){
        mid = (l+r)/2;
        num = 0LL;
        for(auto box : boxes){
            if(mid<box.begin) continue;
            num += ((mid>box.end?box.end:mid)-box.begin)/box.interval+1;
        }
        if(num<d) l=mid+1;
        else if(num>=d){
            r=mid-1;
            m = min(m,mid);
        }
    }

    for(auto box : boxes){
        if(box.begin<=m)
            ans = max(ans, box.begin+((m-box.begin)/box.interval)*box.interval);
    }

    printf("%d",ans);
    return 0;
}