[백준/BOJ] 백준 17383번 : 옥토끼는 통신교육을 풀어라!!

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

17383번: 옥토끼는 통신교육을 풀어라!!

이분 탐색을 이용하여 해당 시간(check)으로 문제를 해결하는 간격을 만들 수 있는지 확인하여 문제를 해결했다. 문제를 끝내는 시간을 check, check*2, check*3... 시간에 맞추는 것으로 확인했다. check시간 이하에 풀 수 있는 문제를 하나의 블록으로 생각하여, 블록 두 줄(한 번에 동시에 두 개의 문제를 풀 수 있으므로)의 차이가 블록 한 개 이하로 되도록 블록을 쌓아가는 방식으로 문제를 해결했다.

 

블록을 쌓는 과정 예시

 

코드

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

int n;
vector<int> inputs;

//check시간으로 문제를 해결하는 간격을 만들 수 있는지 확인
//check, check*2, check*3... 시간에 문제를 끝내는 시간을 맞추는것으로 확인한다
//check시간 이하에 풀 수 있는 문제를 1블록으로 생각한다
//첫번째 문제 해결 이후 stack_block에는 1(하나의 블록크기)이 쌓여있어야 하고
//다음부터 문제를 풀때 stack_block에는 해당 문제 블록 - 1개가 쌓여 있도록 sava_block에 저장된 블록을 빼서 해결한다
bool Solve(int check)
{
	int save_block = 0;
	int stack_block = 0;

	for (int i = 0; i < inputs.size(); i++)
	{
		//첫번째 문제일때
		if (i == 0)
		{
			//제일 작은 문제를 해결하지 못할때
			if (inputs[i] > check)
				return false;

			else
			{
				stack_block++; //1블록짜리가 하나 쌓이게 된다
			}

			continue;
		}

		//문제 자체가 check시간 이하로 걸릴때 (한 블록으로 해결될때)
		//해당 문제는 무조건 풀 수 있으므로 해당 블록을 저장해 놓는다
		if (inputs[i] <= check)
		{
			save_block++; //해당 문제를 하나의 블록으로 저장해 놓는다 (필요할때 빼서 쓸 수 있음)
			continue;
		}

		//두개 이상의 블록으로 해결이 될때

		int this_block = (inputs[i] / check);

		if (inputs[i] % check != 0) //해당 문제 시간이 check로 나누어 떨어지지 않을때
			this_block++;

		//this_block을 해결하기 위해서는 stack_block을 this_block - 1개로 만들수 있어야 한다
		//stack_block을 this_block - 1개로 만들 수 있을때
		if (stack_block + save_block >= this_block - 1)
		{
			//stack_block을 this_block - 1로 만드는데 필요한 블록의 양
			int need_block = (this_block - 1) - stack_block;

			save_block -= need_block;
			stack_block += need_block;

			stack_block = (this_block - stack_block); //stack_block이 1이 된다
		}

		//stack_block을 this_block - 1개로 만들 수 없을때
		else
			return false;

	}
	return true;
}

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

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		inputs.push_back(input);
	}

	sort(inputs.begin(), inputs.end());

	int left = 1;
	int right = inputs[inputs.size() - 1];
	int result = -1;

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

		if (Solve(mid) == true)
		{
			result = mid;

			right = mid - 1;
		}

		else
		{
			left = mid + 1;
		}
	}

	cout << result;

	return 0;
}