[백준 1780] 종이의 개수

분류 

분할 정복

요구사항

1. 9칸으로 나누었을때 가장 작게 나누어지는 조각 찾기

2. 각 조간의 갯수 구하기

 

풀이

나는 어려운데 정답률이 상당히 높다

문제 풀이의 흐름은

검사 -> 분할으로 진행된다

검사는 현재 나눈 칸이 동일한 값으로 이루어 져있는지 검사하는 단계

분할은 동일한 값이 아니라면, 9칸으로 나누어서 다시 진행하는 것이다

 

분할하는 것이 힘들었다

9칸을 어떻게 나눌것인가

풀이는 직접 그려보고 index 번호 적어보니깐 어떻게 나눌지 보이기 시작했다

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <string.h>
#include <queue>

using namespace std;
int map[2200][2200];
int n;
int ans[3];
bool check(int r, int c, int nowsize) {
	int nownum = map[r][c];
	for (int i = r; i < r + nowsize; i++) {
		for (int j = c; j < c + nowsize; j++) {
			if (map[i][j] != map[r][c]) return false;
		}
	}
	return true;
}
void solve(int r, int c, int nowsize) {
	if (check(r, c, nowsize)) {
		ans[map[r][c] + 1]++;
		return;
	}
	else {
		int nextsize = nowsize / 3;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				solve(r + nextsize*i, c + nextsize*j, nextsize);
			}
		}
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%d", &map[i][j]);
	solve(0, 0, n);
	cout << ans[0] << endl;
	cout << ans[1] << endl;
	cout << ans[2] << endl;
}