백준(BAEKJOON ONLINE JUDGE) 2630 색종이 만들기 풀이

사용언어

Visual studio 2019 C++

문제링크 : https://www.acmicpc.net/problem/2630

문제풀이

같은 색으로만 이루어진 정사각형의 종이로 잘라야 하는 문제이당

#include <iostream>

using namespace std;

int N;
int arr[128][128];
int p1, p2;

void paper(int a, int b, int n) {
	bool bo = true;
	int d = arr[a][b];
	for (int i = a; i < a + n; i++) {
		if (bo)
			for (int j = b; j < b + n; j++) {
				if (arr[i][j] != d) {
					bo = false;
					break;
				}
			}
	}

	if (bo) { // 모두 같은 색으로 이루어져있으면!
		if (d)
			p2++;
		else
			p1++;
	}
	else { // 아닐경우 또 4개로 잘라야함!
		paper(a, b, n / 2);
		paper(a + n / 2, b, n / 2);
		paper(a, b + n / 2, n / 2);
		paper(a + n / 2, b + n / 2, n / 2);
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> arr[i][j];
	
	p1 = 0, p2 = 0;
	paper(0, 0, N);
	cout << p1 << "\n" << p2;
}