백준 2630번: 색종이 만들기 (C++)

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

2630번: 색종이 만들기

 

 

풀이

1780 종이의 개수와 거의 비슷한 문제.

 

paper[2] 에 각각의 종이의 개수를 넣어주었다.

 

partition 함수를 보면, 종이를 전부 탐색하고 가장 왼쪽 상단의 숫자와 다른 숫자가 있을 때 chk를 체크해주었다.

chk에 따라 전체가 같은 색이면 paper[]의 숫자를 추가시켰다.

 

그리고 하나라도 다른 부분이 있을 경우 4가지 부분으로 나누어서 똑같이 반복 시켰다.

 

전체 코드

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int N;
int board[200][200] = { 0, };
int paper[2] = { 0, };

void partition(int y, int x, int n) {
	bool chk = true;
	for (int i = x; i < x + n; i++) {
		for (int j = y; j < y + n; j++) {
			if (board[x][y] != board[i][j]) chk = false;
		}
	}

	if (chk) paper[board[x][y]]++;
	else {
		partition(y, x, n / 2);
		partition(y + (n / 2), x, n / 2);
		partition(y, x + (n / 2), n / 2);
		partition(y + (n / 2), x + (n / 2), n / 2);
	}
}

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) cin >> board[i][j];
	}

	partition(0, 0, N);
	cout << paper[0] << '\n' << paper[1];
}