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

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

15732번: 도토리 숨기기

해당 위치까지의 도토리의 개수가 d개 이상인지 확인하는 이분 탐색을 이용해 문제를 해결했다.

 

코드

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

int n, k, d;
vector<tuple<int, int, int>> rule;

//mid위치까지의 도토리의 개수가 d개 이상인지 확인
bool Check(int mid)
{
	long long cnt = 0;
	for (int i = 0; i < rule.size(); i++)
	{
		int a = get<0>(rule[i]);
		int b = get<1>(rule[i]);
		int c = get<2>(rule[i]);

		int this_cnt;

		//mid까지 위치에 해당 규칙에 의해 도토리가 있지 않을때
		if (mid < a)
			this_cnt = 0;

		//mid가 a와 b사이에 있을때 -> mid까지 해당 규칙의 도토리의 개수를 구한다
		else if (mid <= b)
			this_cnt = ((mid - a) / c) + 1;

		//mid가 해당 규칙의 범위보다 커서 해당 규칙의 도토리가 모두 들어갈때
		else
			this_cnt = ((b - a) / c) + 1;

		cnt += (long long)this_cnt;
	}

	if (cnt >= d)
		return true;

	return false;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> k >> d;

	for (int i = 0; i < k; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;

		rule.push_back(make_tuple(a, b, c));
	}

	int left = 1;
	int right = n;
	int result = -1;

	while (left <= right)
	{
		int mid = (left + right) / 2;

		if (Check(mid) == true)
		{
			result = mid;
			right = mid - 1;
		}

		else
		{
			left = mid + 1;
		}
	}

	cout << result;

	return 0;
}