백준 1780 종이의 개수

 

문제 : https://www.acmicpc.net/problem/1780

 

서론

이 문제는 분할정복문제.

그러나 시간초과가 날것같은 예감에 다른풀이가 있는지 생각해보았으나 떠오르지 않았다.

결국 일반적인 재귀를 이용한 분할정복으로 풀었더니 통과.

 

아이디어

재귀함수, 분할정복에 대한 사전이해가 필요

 

계산의 편의를 위해 +2한 입력변수를 전부 n*n배열에 넣고

n*n범위내의 수가 전부 같은 수이면 종이의 개수를 +1 하고

아니라면 종이를 9등분하는 재귀함수를 생성

재귀함수는 9등분된 종이가 배열 한칸의 크기가 될때까지 반복

 

구현

// c++

#pragma warning (disable:4996)

#include <iostream>
#include <cstdio>

using namespace std;

int n;
int paper[2188][2188];
int result[4]; // 1, 2, 3 사용

void recursive(int y, int x, int nn) {
	int check = paper[y][x];
	if (nn == 1) {
		result[check]++;
		return;
	}

	bool recFlag = false;

	for (int i = 0; i < nn; i++) {
		for (int j = 0; j < nn; j++) {
			if (check != paper[i + y][j + x]) { 
				recFlag = true; 
				break;
			}
		}
		if (recFlag == true) break;
	}

	if (recFlag == true) {
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				recursive(y + nn * i / 3, x + nn * j / 3, nn / 3);
			}
		}
	}
	else {
		result[check]++;
	}
	return;
}

int main() {
	scanf("%d", &n);
	int tmp = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &tmp); // -1,0,1 -> 1,2,3
			paper[i][j] = tmp + 2;
		}
	}
	recursive(0, 0, n);
	for (int i = 1; i < 4; i++) cout << result[i] << endl;
}