백준 2630

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

2630번: 색종이 만들기

처음에 이문제를 보았을 때 분할 정복을 사용해서 풀면은 될거같다는 느낌을 팍팍 풍기는 그림이 그려져 있었다.

이에 분할정복을 처음 사용 할때 나는 파란종이와 흰종이를 구하는 함수 2개를 만들어서 실행시켰다. 하지만 실행 시키고나니 시간초과가 발생하였다. 이에 시간 초과를 발생시키지 않기 위해서 파란색 종이를 구하면서 하얀색 종이를 구할 수 있도록 작성했다

#include <iostream>
using namespace std;
int N;
int bCnt;
int wCnt;
int arr[128][128];
int bSolution(int x, int y , int size) {
	if (size == 0) {
		return 0;
	}
	int check=0;
	for (int i = x; i < x+size; i++) {
		for (int j = y; j < y+size; j++) {
			if (arr[i][j] != 1) {
				check = 1;
				break;
			}
		}
		if (check == 1)
			break;
	}
	if (check == 1) {
		for (int i = x; i < x + size; i++) {
			for (int j = y; j < y + size; j++) {
				if (arr[i][j] != 0) {
					check = 2;
					break;
				}
			}
			if (check == 2)
				break;
		}

	}
	if (check == 0) {
		bCnt++;
	}
	else if (check == 1) {
		wCnt++;
	}
	else {
		bSolution(x, y, size / 2);
		bSolution(x, y + size / 2, size / 2);
		bSolution(x + size / 2, y, size / 2);
		bSolution(x + size / 2, y + size / 2, size / 2);
	}
	return 0;
}

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

	bSolution(0, 0, N);
	cout << wCnt<<endl;
	cout << bCnt << endl;
}

위에 코드를 보면 check라는 변수가 존재 한다 나는 check가 0일 때는 파란색종이의 갯수를 구하다 check가 1로바뀌면 흰종이를 check가 2로 해당영역이 파란종이도 흰종이도 아닌것이라고 파악했다 이경우 분할을 통해 다시 색종이의 갯수를 구한다.

	for (int i = x; i < x+size; i++) {
		for (int j = y; j < y+size; j++) {
			if (arr[i][j] != 1) {
				check = 1;
				break;
			}
		}
		if (check == 1)
			break;
	}

이부분은 해당영역에 0이 하나라도 있으면 break 한다 그럼 일단 파란종이는 아니다

	if (check == 1) {
		for (int i = x; i < x + size; i++) {
			for (int j = y; j < y + size; j++) {
				if (arr[i][j] != 0) {
					check = 2;
					break;
				}
			}
			if (check == 2)
				break;
		}

	}

이부분은 일단 파란종이가 아니니 흰종이인지 검사한다 이부분에서 0이 하나라도 발견되면 흰종이가 아니니 이제 모드를 check2로 바꾸고 분할정복을 시행한다. 확실히 회사일을 하다보니 알고리즘 실력은 줄었으나 뭔가를 생각하고 구현을 하는 능력은 올라간거 같다