분할정복 - 백준 1780번 종이의 개수

www.acmicpc.net/problem/1629

1629번: 곱셈

IDEA

2630번 색종이 만들기 ( blahblahlab.tistory.com/63 ) 와 같은 문제다. 

분할을 4등분이 아닌 9등분으로 해주면 된다. 

 

CODE 

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

int arr[3000][3000];
int k, m_count = 0, p_count = 0 , z_count = 0;

void divide(int x, int y, int n){
	//개수 세기
	int p=0, z=0, m = 0;
	for (int i = x; i <x+ n; i++) {
		for (int j = y; j <y+ n; j++) {
			if (arr[i][j] == 1) p++;
			else if (arr[i][j] == 0) z++;
			else m++;
		}
	}
	//숫자 하나로만 이루어져있는지 확인 
	if (p == n * n || z == n * n || m == n * n) {
		if (p == n * n) p_count++;
		else if (z == n * n) z_count++;
		else m_count++;
		return;
	}
	//숫자 하나로만 이루어져있지 않다면 /9
	else {
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				divide(x  + (n/ 3) * i , y + (n/3) * j , n / 3);
			}
		}
	}
}

int main() {
	scanf("%d", &k);
	for (int i = 0; i < k; i++) {
		for (int j = 0; j < k; j++) {
			scanf("%d", &arr[i][j]);
		}
	}
	divide(0, 0, k);
	printf("%d\n", m_count);
	printf("%d\n", z_count);
	printf("%d\n", p_count);
}