[백준/BOJ] 백준 10227번 : 삶의 질

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

10227번: 삶의 질

h*w 영역에서 중간값의 수의 크기가 가장 작은 값을 찾는 방법은 이분 탐색을 이용했는데, 이분 탐색에서 체크할 때, 해당 수의 값 이하에서 중간값이 되는 게 있는지 확인하여, 있으면 right를 mid - 1로 옮기고, 없으면 left를 mid + 1로 옮기는 방법을 이용했다. 해당 수의 값 이하에서 중간값이 되는게 있는지 확인하는 방법은, board의 크기와 같은 check를 만들어, 확인하는 숫자와 같은 수는 0, 확인하는 수 보다 작은 수는 -1, 확인하는 수보다 큰 수는 1로 채워 넣고, check의 2차원 누적합을 만든 뒤, 해당 누적합을 이용해서 h*w 크기의 구간에서 0이하의 값이 나오는 구간이 있는지 확인하는 방법을 통해 문제를 해결했다.

 

코드

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

int r, c;
int h, w;
int board[3001][3001];
int check[3001][3001];
int psum[3001][3001];

//mid 이하의 값에서 중간값이 되는게 있는지 확인
bool Solve(int mid)
{
	//check에 mid는 0, mid보다 작은것은 -1, mid보다 큰것은 1로 체크한다
	for (int i = 1; i <= r; i++)
	{
		for (int j = 1; j <= c; j++)
		{
			if (board[i][j] == mid)
				check[i][j] = 0;
			else if (board[i][j] < mid)
				check[i][j] = -1;
			else
				check[i][j] = 1;
		}
	}

	//check의 2차원 누적합을 만든다
	for (int i = 1; i <= r; i++)
	{
		for (int j = 1; j <= c; j++)
		{
			psum[i][j] = check[i][j] + psum[i][j - 1] + psum[i - 1][j] - psum[i - 1][j - 1];
		}
	}

	//만든 2차원 누적합에서 h*w크기의 합이 0이하인 구간이 있는지 찾는다
	//해당 구간의 합이 0이면, mid가 중간값인 구간인것이고 
	//해당 구간의 합이 음수이면 mid보다 작은 값이 중간값인 구간인것이다
	for (int i = h; i <= r; i++)
	{
		for (int j = w; j <= c; j++)
		{
			if (psum[i][j] - psum[i][j - w] - psum[i - h][j] + psum[i - h][j - w] <= 0)
				return true;
		}
	}

	return false;
}

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

	cin >> r >> c >> h >> w;

	for (int i = 1; i <= r; i++)
	{
		for (int j = 1; j <= c; j++)
		{
			int input;
			cin >> input;

			board[i][j] = input;
		}
	}

	int left = 1;
	int right = r * c;
	int result = -1;

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

		//mid 이하의 값에서 중간값이 되는게 있는지 확인
		if (Solve(mid))
		{
			result = mid;

			right = mid - 1;
		}

		else
		{
			left = mid + 1;
		}

	}

	cout << result;

	return 0;
}