15732번-도토리숨기기

문제

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

15732번: 도토리 숨기기

---

접근방법

이 문제는 어떤 것을 탐색 기준으로 삼아야 할 지 어려웠던 문제였다. 탐색 기준은 "박스의 최대 길이"로 설정하여서 이분 탐색을 수행하였다. 박스의 최대 길이와 규칙에서 더 짧은 기준을 선정하여 check 함수 탐색의 right값을 설정하였다.(앞에서 부터 갯수를 세는 문제 조건) 

그 이후 mid 값을 줄여서 최소의 mid로 도토리가 D이상이 되게 구하면 된다.

---

정답코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 1e6 + 1;
ll n, k, d;
 
struct info{
    ll start;
    ll end;
    ll width;
};
 
vector<info> v;
 
bool check(ll mid)
{
    ll cnt = 0;
    for(int i = 0; i < k; i++)
    {
        //앞에서 부터 도토리를 담으므로 가장 끝에 도토리가 있게 하기 위해서는 mid값을 줄여줘야한다. 그러므로 가능한 최소의 경우를 다룬다.
        ll right = min(v[i].end, mid);
        if(right >= v[i].start)
            //너비에서 몇 개의 도토리를 담을 수 있는가
            cnt += ((right - v[i].start) / v[i].width) + 1;
    }
    return cnt >= d;
}
 
int main(void)
{
    fastio;
    cin >> n >> k >> d;
    v.resize(MAX);
    //규칙 담기
    for(int i = 0; i < k; i++)
        cin >> v[i].start >> v[i].end >> v[i].width;
 
    ll left = 0;
    ll right = n;
    while(left + 1 < right)
    {
        ll mid = (left + right) / 2;
        //박스가 mid개일 경우 도토리를 d개 이상 담을수 있는가
        if(check(mid))
            right = mid;
        else
            left = mid;
    }
    cout << right << "\n";
}