C++ [백준]2630번 색종이 만들기

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

2630번: 색종이 만들기

 

분명 class3은 다 풀었는데, solved에 안풀었다고 되어있어서, 연습삼아 한 번 더 풀어보고 이렇게 올립니다!

 

 

솔루션

---

2^N의 수가 들어오는데, 128까지 밖에 안들어와서 입력이 꽤나 작다.

 

나는 먼저, 해당 정사각형을 탐색을 해서 하나라도 다른 것이 있는지 없는지 판단을 한다.

만약 다른 것이 있다면 4개로 분할 하고

 -> x,y

 -> x+size/2,y

 -> x, y+size/2

 -> x+size/2, y + size/2

 

만약 전부 똑같다면 [x][y]의 지점에 있는 것의 색깔을 ++시켜주었다.

 

그리고 size==1이라면 바로 [x][y]의 색을 올려주고 return 시켰다.

 

 

다시 풀어보니 분할정복 문제의 아주 좋은 문제 인 것 같다.

 

 

코드

---

#include <iostream>
using namespace std;

int N;
int arr[129][129];

int white;
int blue;
void calcCnt(int x, int y, int size) {
	if (size == 1) {
		if (arr[x][y]) blue++;
		else white++;
		return;
	}
	bool is_dif = false;
	for (int i = x; i < x+size && !is_dif; i++) {
		for (int j = y; j < y+size; j++) {
			if (arr[x][y] != arr[i][j]) {
				is_dif = true;
				break;
			}
		}
	}

	if (!is_dif) {
		if (arr[x][y]) blue++;
		else white++;
		return;
	}
	else {
		calcCnt(x, y, size / 2);
		calcCnt(x + size / 2, y, size / 2);
		calcCnt(x, y + size / 2, size / 2);
		calcCnt(x + size / 2, y + size / 2, size / 2);
		return;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
		}
	}

	calcCnt(0, 0, N);

	cout << white << "\n" << blue << "\n";
}