[백준 15732] 도토리 숨기기

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

와!! 이분탐색 문제중에 처음으로 보자마자 슥슥 접근하고 바로 구현해냈다..
사실 규칙이 쉬워서 금방 발견한거긴 하지만..

문제 풀이

우선 문제가 요구하는 값은 '마지막 도토리가 들어가는 상자의 번호'이다.
마지막 도토리라는 것은 D번째 도토리라는 것이다.
도토리 D가 있을때, 1~i번째 상자까지의 도토리의 합이 D가 된다면 마지막 상자가 된다는 것도 알 수 있다. 그리고 마지막 상자는 결국 '최댓값'이다.
와! 앞서 풀었던 파라메트릭 서치 문제인 것이다.

그렇다면 i번째의 상자까지의 도토리 D개는 어떻게 알 수가 있을까?
'규칙대로'더해보면 되지 않을까?
규칙을 보면 C번마다 반복하여 도토리를 추가하는 것을 알 수 있었다.즉 C로 나누기를 하면 된다. 다만 시작값과 끝 값이 정해져 있으니 이를 유의해서 계산해주면 된다.

구현

#include <iostream>
#include <vector>
using namespace std;

struct rule
{
	int s,e,j;
	rule(int s,int e, int j):s(s),e(e),j(j){};
};


int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
    int result;
    int n, k;
	int d;
    cin>>n>>k>>d;
    int s=0,&e=n;
    vector <rule> rule;
    for(int i=0; i<k; i++){
        int a,b,c;
        cin>>a>>b>>c;
        rule.push_back({a,b,c});
    }
    while (s<=e)
    {
        long long cnt=0;
        int m = (s+e)/2;
        for(auto&r : rule){
            if(m < r.s) continue;
			cnt += (min(m,r.e)-r.s)/r.j + 1;
        }
        if(cnt<d){
            s=m+1;
        }
        else{
			result=m;
            e=m-1;
        }
    }
    cout<<result;
    
    return 0;
}