색종이 만들기[백준 :2630]실버

 

종이 자르기 문제

 

위처럼 종이가 주어지면 흰색 부분과 파란 부분을 분리하여 자르되

정사각형이 되도록  자르는게 목적이다.

 

해당 문제는 한칸씩 확인하며 정사각형을 측정한다면

틀렸을때 최적이 될 정사각형을 찾아야 하기에

 

중복 되는 탐색이 매우 많을 것 같은 느낌이다.

 

이문제는 모든 사각형을 정사각형으로 자른다가 핵심이라고 생각한다.

 

가장 큰 종이에서 나올 수 있는 최대 정 사각형은 4개 그 안에서도 4개로 오히려 쪼개면서 계산하는 것이다.

 

사실 문제에서 내용을 이미지로 간단하게 설명해준다.

 

위 이미지 순서대로 큰거 자르고 문제 있는 부분만 자르면서 들어가는식으로 풀면된다

 

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

vector<vector<int>> arrya;
int color[2] = {0,0};

//재귀함수
void Recursive(int size, int x, int y) {
	int  a = arrya[x][y];
	bool is_same = false;
	
    //해당 크기의 정사각형 완전탐색하며 문제있는지 확인
    for (int i = x; i < x + size; i++) {
		for (int j = y; j < y + size; j++) {
			if (arrya[i][j] != a)
			{
				is_same =true;
				break;
			}
		}
		if (is_same)break;
	}
    //정사각형 4개로 나눠서 재귀
	if (is_same) {
		size /= 2;
		Recursive(size, x, y);
		Recursive(size, x + size, y);
		Recursive(size, x, y + size);
		Recursive(size, x + size, y + size);
	}
	else {
    //다채워졌다면 사각형이니 +1
		color[a]++;
	}





}



void solution() {
	int size;
	cin >> size;
	arrya = vector<vector<int>>(size);

	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			int z = 0;
			cin >> z;
			arrya[i].push_back(z);
		}
	}
	Recursive((size ), 0, 0);
	cout << color[0] << "\n"<<color[1];




}

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


	solution();
	return 0;
}