[백준/BOJ] 백준 5821번 : 쌀 창고

www.acmicpc.net/problem/5821

5821번: 쌀 창고

mid개의 논에서 쌀 창고로 옮길 수 있는지 확인하는 이분 탐색을 이용해 문제를 해결했다. 확인하는 함수는 Check(long long check_cnt)를 통해 만들었고, check_cnt개의 논에서 쌀 창고로 옮길 수 있는 구간(check_cnt개의 연속된 논들)을 확인한다. 주의해야 될 점은 구간의 중앙 인덱스(구간의 논들의 위치 중 중앙 논의 위치)가 쌀 창고가 되는 게 최적이라는 점이다. 그리고 그때 드는 비용은 왼쪽 구간, 오른쪽 구간의 개수와 누적합을 이용해 문제를 해결했다.

 

코드

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

long long r, l, b;
vector<long long> x(100001, 0);
vector<long long> psum(100001, 0);

bool Check(long long check_cnt)
{
	//check_cnt개의 논에서 쌀 창고로 옮길 수 있는 구간(check_cnt개의 연속된 논들)을 확인한다
	for (long long i = 1; i + check_cnt - 1 <= r; i++)
	{
		long long range_left_index = i; //확인하는 구간의 왼쪽 끝
		long long range_right_index = i + check_cnt - 1; //확인하는 구간의 오른쪽 끝
		long long range_mid_index = (range_left_index + range_right_index) / 2; //구간에서 가운데 인덱스, 이 곳이 쌀 창고의 위치가 된다 (구간의 중앙 인덱스가 쌀 창고가 되는게 최적)

		long long range_mid_before_index = range_mid_index - 1;

		long long left_cnt = range_mid_index - range_left_index; //구간에서 range_mid_index 왼쪽에 있는 논들의 개수
		long long right_cnt = range_right_index - range_mid_index; //구간에서 range_mid_index 오른쪽에 있는 논들의 개수

		long long left_cost = (x[range_mid_index] * left_cnt) - (psum[range_mid_before_index] - psum[range_left_index - 1]); //쌀 창고 왼쪽의 논들에서 쌀 창고로 오는 비용
		long long right_cost = (psum[range_right_index] - psum[range_mid_index]) - (x[range_mid_index] * right_cnt); //쌀 창고 오른쪽의 논들에서 쌀 창고로 오는 비용

		if (left_cost + right_cost <= b) //예산 안으로 가능할때
		{
			return true;
		}

	}

	return false;
}

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

	cin >> r >> l >> b;

	//i번째 논을 i번째 인덱스에 저장
	for (long long i = 1; i <= r; i++)
	{
		long long input;
		cin >> input;

		x[i] = input;

		psum[i] = psum[i - 1] + input;
	}

	long long left = 1;
	long long right = r;
	long long result = 0;

	while (left <= right)
	{
		long long mid = (left + right) / 2; //mid개의 논에서 쌀 창고로 옮길 수 있는지 확인

		if (Check(mid) == true)
		{
			result = mid;
			left = mid + 1;
		}

		else
			right = mid - 1;
	}

	cout << result;

	return 0;
}