[10227번 삶의 질] - C++

[10227번 삶의 질]
https://www.acmicpc.net/problem/10227

삶의 질이 떨어지는 문제였다. 매우 어려웠고 풀지 못해서 풀이를 찾아봤다.
이 문제를 풀기 위해서는 2차원 누적합과 이분 탐색에 대해 알고 있어야 한다. 이 정도 난이도의 문제를 풀려고 하는 분들은 모두 알고 있을 거라 생각하지만 까먹었을 수도 있으니 가벼운 관련 몸풀기 문제 2개를 첨부한다.

[2167번 2차원 배열의 합]
https://www.acmicpc.net/problem/2167

[2805번 나무 자르기]
https://www.acmicpc.net/problem/2805

풀이

mid 값 정하기

일단 중간값은 1 ~ R*C로 정해져 있기 때문에 이분 탐색을 떠올릴 수 있다. 그러면 대충 요런 코드가 짜여질 수 있다.

int mid;
int l = 0, r = R*C;
while(l+1 < r) {
    mid = (l+r) / 2;
    if(sol()) {
    	// when mid could be a correct value
        r = mid;
    } else {
    	// when mid cannot be a correct value
        l = mid;
    }
}

이분 탐색 구현에 관해서는 개개인의 구현 방식이 다르기 때문에 대략 이런 식으로 시작한다는 점만 생각하면 될 것 같다.

sol() 메서드 안에서 mid 의 값이 올바른 중간값이 될 수 있는지를 판단해야 한다. 중간값 여부를 판단하는데 O(R*C) 만큼의 시간 복잡도가 소요된다면 전체적으로 답을 구하는 데 O(RClog(RC)) 만큼의 시간 복잡도가 소요된다(mid 을 이분 탐색하는데 O(log(RC)) 만큼 소요). R*C 의 값이 최대 900만이므로 약 2억 정도의 연산이 필요하고 이는 시간제한 5초 안에 들어올 수 있다는 계산이 나온다.

중간값 여부 판단

중간값 여부를 판단하기 위해서 2차원 누적합을 사용한다.
bd[R][C] , check[R][C] , psum[R][C] 2차원 배열을 미리 만들어 두고,

bd[i][j] 값이 mid 값과 같으면 0, 작으면 -1, 크면 1을 check[i][j] 값으로 설정한다.

sol() {
	for(int i=1;i<=R;++i) {
    	if(bd[i][j] == mid) check[i][j] = 0;
        else if(bd[i][j] < mid) check[i][j] = -1;
        else if(bd[i][j] > mid) check[i][j] = 1;
    }
}

check 배열의 값을 가지고 psum 배열에 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];
    }
}

이제 판단을 위한 준비는 끝났다. i=H, j=W 부터 범위를 순회하며 누적합이 0보다 같거나 작아지는 경우 true 를 반환한다. 그런 영역이 하나도 없다면 false 를 반환한다.

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;

이렇게 하면 O(RC) 시간 복잡도에 중간값 여부를 판단할 수 있다.

C++ 코드

#include <bits/stdc++.h>

#define ll long long
using namespace std;
typedef pair<int,int> pint;
typedef vector<int> vint;
const int INF = 0x3f3f3f3f; const int mINF = 0xc0c0c0c0;
const ll LINF = 0x3f3f3f3f3f3f3f3f; const ll mLINF = 0xc0c0c0c0c0c0c0c0;

int ans;
int R,C,H,W;
int bd[3001][3001], check[3001][3001], psum[3001][3001];
int mid;

bool sol() {
	for(int i=1;i<=R;++i) {
		for(int j=1;j<=C;++j) {
			if(bd[i][j] == mid) check[i][j] = 0;
			else if(bd[i][j] < mid) check[i][j] = -1;
			else if(bd[i][j] > mid) check[i][j] = 1;
		}
	}

	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];
		}
	}
	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() {
	// ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	scanf("%d %d %d %d", &R, &C, &H, &W);
	for(int i=1;i<=R;++i) {
		for(int j=1;j<=C;++j) {
			scanf("%d", &bd[i][j]);
		}
	}
	int l = 0, r = R*C;
	while(l+1 < r) {
		mid = (l+r)/2;
		if(sol()) {
			ans = mid;
			r = mid;
		} else {
			l = mid;
		}
	}
	printf("%d\n", ans);
	return 0;
}

실행 결과