[Baekjoon, C++] 1780번 : 종이의 개수

백준 단계별 풀기에서 분할정복 세 번째 문제이다.

링크는 아래와 같다.

www.acmicpc.net/problem/1780

1780번: 종이의 개수

---

백준 1780번 문제, 입력, 출력

---

백준 1780번 입출력 예제 1

---

1. 분할정복 문제는 재귀함수의 활용이다. 분할정복 첫 문제를 해결하니, 두 번째 문제도 그렇고 이번 문제도 그렇고 굉장히 쉽게 해결하였다. 앞선 문제들이 배열 0과 1의 두 가지 변수만을 사용했다면, -1, 0, 1의 3가지 변수를 설정하고 접근하면 된다. 그리고 기존의 정사각형을 4등분 한것을 바탕으로, 이번에는 9등분을 하면 되었다. 즉, 9번의 재귀함수를 call 하면 된다.

 

2. 두 번째 문제 였던 쿼드트리에서 겪었던 문제를 다시 겪었다. 이번에는 조금 다른게 cin.get()을 이용해서 받을 때, '틀렸습니다'를 출력하였고, cin을 통해서 받았을 때 '맞았습니다' 를 볼 수 있었다.

---

틀렸습니다.

#include<iostream>

using namespace std;

int paper[2188][2188];
int minusOne = 0, zero = 0, plusOne = 0;

void numOfPaper(int x, int y, int N) {
	int tmpMinusOne = 0;
	int tmpPlusOne = 0;
	for (int i = x; i < x + N; i++) {
		for (int j = y; j < y + N; j++) {
			if (paper[i][j] == 1) {
				tmpPlusOne++;
			}
			if (paper[i][j] == -1) {
				tmpMinusOne++;
			}
		}
	}
	if (tmpPlusOne == N * N) plusOne++;
	else if (tmpMinusOne == N * N) minusOne++;
	else if (tmpPlusOne == 0 && tmpMinusOne == 0) zero++;
	else {   // 쪼갬=재귀	
		numOfPaper(x, y, N / 3);  // 왼쪽 위 사각형
		numOfPaper(x, y + N / 3, N / 3); // 중간 위 사각형
		numOfPaper(x, y + N * 2 / 3, N / 3); // 오른쪽 위 사각형
		numOfPaper(x + N / 3, y, N / 3); // 왼쪽 중간 사각형
		numOfPaper(x + N / 3, y + N / 3, N / 3); // 중간 중간 사각형
		numOfPaper(x + N / 3, y + N * 2 / 3, N / 3); // 오른쪽 중간 사각형
		numOfPaper(x + N * 2 / 3, y, N / 3); // 왼쪽 아래 사각형
		numOfPaper(x + N * 2 / 3, y + N / 3, N / 3); // 중간 아래 사각형
		numOfPaper(x + N * 2 / 3, y + N * 2 / 3, N / 3); // 오른쪽 아래 사각형		
	}
	return;
}

int main() {
	/*ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);*/
	int n;
	char tmp;

	cin >> n;
	cin.get();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin.get(tmp);
			paper[i][j] = tmp - 48;
		}
		cin.get();
	}
	/*int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> paper[i][j];
		}
	}*/

	numOfPaper(0, 0, n);

	cout << minusOne << "\n";
	cout << zero << "\n";
	cout << plusOne << "\n";

	return 0;
}

---

맞았습니다.

  #include<iostream>

using namespace std;

int paper[2188][2188];
int minusOne = 0, zero = 0, plusOne = 0;

void numOfPaper(int x, int y, int N) {
	int tmpMinusOne = 0;
	int tmpPlusOne = 0;
	for (int i = x; i < x + N; i++) {
		for (int j = y; j < y + N; j++) {
			if (paper[i][j] == 1) {
				tmpPlusOne++;
			}
			if (paper[i][j] == -1) {
				tmpMinusOne++;
			}
		}
	}
	if (tmpPlusOne == N * N) plusOne++;
	else if (tmpMinusOne == N * N) minusOne++;
	else if (tmpPlusOne == 0 && tmpMinusOne == 0) zero++;
	else {   // 쪼갬=재귀	
		numOfPaper(x, y, N / 3);  // 왼쪽 위 사각형
		numOfPaper(x, y + N / 3, N / 3); // 중간 위 사각형
		numOfPaper(x, y + N * 2 / 3, N / 3); // 오른쪽 위 사각형
		numOfPaper(x + N / 3, y, N / 3); // 왼쪽 중간 사각형
		numOfPaper(x + N / 3, y + N / 3, N / 3); // 중간 중간 사각형
		numOfPaper(x + N / 3, y + N * 2 / 3, N / 3); // 오른쪽 중간 사각형
		numOfPaper(x + N * 2 / 3, y, N / 3); // 왼쪽 아래 사각형
		numOfPaper(x + N * 2 / 3, y + N / 3, N / 3); // 중간 아래 사각형
		numOfPaper(x + N * 2 / 3, y + N * 2 / 3, N / 3); // 오른쪽 아래 사각형		
	}
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	/*int n;
	char tmp;

	cin >> n;
	cin.get();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin.get(tmp);
			paper[i][j] = tmp - 48;
		}
		cin.get();
	}*/
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> paper[i][j];
		}
	}

	numOfPaper(0, 0, n);

	cout << minusOne << "\n";
	cout << zero << "\n";
	cout << plusOne << "\n";

	return 0;
}
  

---

이상으로 1780번 종이의 개수 문제를 마무리 하겠다.