백준 BOJ 15732 - 도토리 숨기기

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

15732번: 도토리 숨기기

도토리가 들어간 상자번호를 구해내는 문제.

간격을 d로 두며, 구간 [a,b] 에서 도토리가 들어가있는 상자의 개수는

min(b,now)/d - a/d +1이다.

now 는 내가 정한 상자번호.

 

/d 로 묶어보면 좀 더 자명해지는데,

(min(b,now) - a)/d + 1로,

b보다 now가 더 작으면 세면 안되는 상자들이 생기기때문에 min으로 한번 걸러준 형태이다.

+1은 그냥 구간 내부 원소개수 구할때 닫힌구간이면 +1해주는 그거 맞다.

 

now가 a[i]보다 작은 케이스가 있는데,

이때 저 식 그대로 계산하면 +1이 나오지만 의도된 식은 0이어야 한다.

따로 코너처리를 해주면 AC를 받을 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
 * 도토리 개수 구하기.
 * 간격 d로 두고, 구간[a,b] 에서 도토리 개수는
 * min(b,now)/d - a/d;
 * 도토리 개수는 단조증가 - 파라메트릭
 */
 
ll N,K,D;
ll a[1234567] = {0};
ll b[1234567] = {0};
ll c[1234567] = {0};

ll cnt(ll k){
	ll cnt = 0;
	for(int i=0; i<K; i++){
		if(k < a[i]) continue;
		cnt += (min(k,b[i])-a[i])/c[i]+1;
	}
	return cnt;
}

ll search(ll s, ll e){
	ll mid = (s+e)/2;
	
	if(s>e) return s;
	
	
	if(cnt(mid) < D) return search(mid+1,e);
	else             return search(s,mid-1);
}

int main(){
	cin >> N >> K >> D;
	for(int i=0; i<K; i++){
		cin >> a[i] >> b[i] >> c[i];
	}
	cout << search(1,1e9);
	
	//cout << cnt(125);
	return 0;
}

 

낫배드