[boj : 2937] 블록 정리

www.acmicpc.net/problem/2937

2937번: 블록 정리

문제 : 블록들이 막 쌓여져 있고 이를 옮겨서 직사각형을 만들고 싶다. 이때 보드의 한칸에 블록이 2개 이상 쌓이면 안되도록 만들어라.

 

해설 : 

www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

이 문제 안풀었으면 반드시반드시반드시 풀고 오세요....(한문제 한문제가 중요하다는 걸 다시 한번 깨달음,,ㅠ)

 

사실 11660 문제와 동일 하다고 보시면 됩니다.

어떤 범위를 잡았을때 그 범위내에 있는 블록의 수를 O(1)만에 알 수 있도록 할 수 있는 '테크닉'이 존재합니다.

이 테크닉을 꼭꼭 기억합시다...(이건 다른 블로그들 보시면 많이 나와있습니다)

 

어쨌든 직사각형을 만들때 넓이는 곧 블록의 총 개수와 같으니 m 이겠죠.

이 m 에서 현재 배치된 블록의 수를 빼면 옮겨야 될 횟수가 나오고 이것이 곧 정답이 됩니다.

 

이때 직사각형을 만들려고 모든 변의 수가 아닌 m의 약수만 확인해서 구하면 되겠죠.

x 와 m/x 가 곧 직사각형의 변의 길이니까요.

 

#include<bits/stdc++.h>

using namespace std;

int n, m;
int board[101][101],dp[101][101];
vector<int> v;

const int INF = (int)1e9;
void get_x();

int main()
{
	int x, y;
	cin >> n >> m;
	for (int i = 0; i < m; i++)cin >> x >> y, board[x][y] = 1;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			dp[i][j] = dp[i - 1][j] - dp[i - 1][j - 1] + dp[i][j - 1]+board[i][j];
	get_x();
	int ans = INF;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			for (int u : v) {
				if (i + u - 1 > n || j + m / u - 1 > n)continue;
				int x1 = i, x2 = i + u - 1;
				int y1 = j, y2 = j + m / u - 1;

				ans = min(ans, m - (dp[x2][y2] - (dp[x1 - 1][y2] + dp[x2][y1 - 1]) + dp[x1 - 1][y1 - 1]));
			}
	cout << ans;
	return 0;
}
void get_x()
{
	for (int i = 1; i * i <= m; i++)
		if (m % i == 0)
			v.push_back(i);
}