세미나(분할정복)

큰 문제를 작은 문제로 쪼개서 해결하는것

 

 

1) 큰문제를 작은문제로 분할

2) 문제가 조건을 만족하거나 더이상 나눠지지 않으면 문제해결

3) 작은문제들의 해답을 통합하여 큰 문제를 해결

 

 

ex)

2630번 색종이 만들기

1. 같은색으로 칠해져있는지 확인한다

1.1 같은색으로 칠해져있지 않다면

나눈다

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


int N;
int arr[256][256];
int color[3];

void go(int size, int Y, int X) {
	if (size == 1) {
		color[arr[Y][X]]++;
		return;
	}
	int check = arr[Y][X];
	for (int i = Y; i < Y + size; i++) {
		for (int j = X; j < X + size; j++) {

			if (arr[i][j] != check) {
				check = -1;
				break;
		}
		}
	}
	if (check == -1) {
		int next_size = size / 2;
		go(next_size, Y, X);
		go(next_size, Y, X + next_size);
		go(next_size, Y + next_size, X);
		go(next_size, Y + next_size, X + next_size);

	}
	else {
		color[check]++;
	}
}

int main(int argc, const char* argv[]) {
	ios::sync_with_stdio();
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> arr[i][j];

		}
	}

	go(N, 1, 1);
	cout << color[0] << '\n' << color[1] << "\n";
	return 0;

}

 

프렉탈

최소단위의 집합

최소단위 얻기

 

 

거듭제곱 알고리즘

연산을 할때마다 나머지 연산을 해줘야함