[BOJ/C++] 백준 28081 - 직사각형 피자

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

28081번: 직사각형 피자

입력 제한이 큰 문제이기 때문에, 일반적인 브루트 포스 알고리즘으로 풀면 안 되고, 이분탐색 알고리즘으로 푼다.

가로 방향과 세로 방향에서의 피자 조각의 크기를 모두 배열에 저장한 다음, 각각의 가로 방향의 길이에 대해서 곱이 K 이하가 되는 세로 방향의 크기의 Upper bound 를 구한다.

이때 세로 방향에서의 피자 조각의 크기는 오름차순 정렬되어있으므로, Upper bound를 찾았다면 그 인덱스가 바로 특정 가로 방향의 크기에서 수용 가능한 세로 방향의 크기의 개수가 되는 것이다. 

 

가령, 첫 번째 예제 입력에서 피자조각의 최대 크기 K = 6이므로, 가능한 피자 조각은 2, 4, 3, 6 총 네개이다. 

(1) 첫 번째 세로 방향의 크기 2에 대해서 곱했을 때 6 이하를 만족시킬 수 있는 가로 방향 크기는 1, 2 총 2개이다. 

(2) 두 번째 세로 방향의 크기 3에 대해서 곱했을 때 6 이하를 만족시킬 수 있는 가로 방향의 크기는 1, 2 총 2개이다.

(3) (1)과 (2)에서 나온 결과를 합하면 4이다.

 

세로 방향의 크기를 순회하는 것을 첫 번째 for문, 그리고 정렬된 가로 방향의 크기를 순회하며 선택 가능한 가로 방향의 크기를 찾는 이분탐색 알고리즘이 두 번째 while문이다. 

따라서 총 알고리즘의 시간복잡도는 O(NlogM), O(MlogN)이 된다.

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

long long w, h, k;

bool check(long long height, long long wide) {
	return height * wide <= k; 
}

int main() {
	cin >> w >> h >> k;
	int n; cin >> n;  // 가로 방향 커팅 개수
	vector<long long > height(n); // 커팅의 세로 위치
	vector<long long > block_h;
	for (int i = 0; i < n; i++) {
		cin >> height[i]; 
		if (i != 0) block_h.push_back(height[i] - height[i - 1]);
		else block_h.push_back(height[i]); 
	}
	block_h.push_back(h - height.back());
	
	int m; cin >> m;  // 세로 방향 커팅 개수
	vector<long long > wide(m);
	vector<long long > block_w;
	for (int i = 0; i < m; i++) {
		cin >> wide[i]; 
		if (i != 0) block_w.push_back(wide[i] - wide[i - 1]);
		else block_w.push_back(wide[i]); 
	}
	block_w.push_back(w - wide.back()); 

	long long ret = 0; 
	sort(block_w.begin(), block_w.end());
	for (int i = 0; i < block_h.size() ; i++) { // height
		long long  left = 0;  //  block_w의 인덱스를 저장
		long long  right = block_w.size() - 1;
		while(left <= right){ // wide
			long long  mid = (left + right) / 2;
			if (check(block_h[i], block_w[mid])) { 
				left = mid + 1; 
			}
			else {
				right = mid - 1; 
			}
		}
		ret += left; 
	}
	cout << ret << endl;
	return 0; 
}