[백준] 1780 종이의 개수(C++)

 

문제 URL:

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

1780번: 종이의 개수

 

다음 문제는 N×N크기의 행렬로 표현되는 종이가 존재할 때, 종이를 규칙에 따라 자르며

-1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구하는 문제이다. 

 

문제를 풀기 위해 divide 함수를 사용하여 영역에 존재하는 숫자가 일치하지 않다면 종이를 잘라주었는데

함수 내부에서 재귀를 사용하여 영역의 숫자가 일치할 때까지 종이를 계속 반복하였다.

코드는 아래와 같다. 

 

이 문제를 예전에도 풀었었는데 그때는 재귀라는 알고리즘을 알지 못해서 (무려 5중..) 중첩 반복문을 사용해서 시간 초과가 났었다.
(아래에 코드 첨부)

---

<재귀를 사용한 코드>

#include <iostream>
using namespace std;

int arr[2200][2200];
int ans[3];  // ans[0]: -1종이의 개수, ans[1]: 0종이의 개수, ans[2]: 1종이의 개수

bool check(int row, int col, int num) {  // 영역의 숫자가 모두 일치하는지 확인
	int first = arr[row][col];  // 가장 왼쪽 상단의 값
	for (int i = row; i < row + num; i++)
		for (int j = col; j < col + num; j++)
			if (arr[i][j] != first)
				return false;
	return true;
}

void divide(int row, int col, int num) {  // 종이 자르기
	if (check(row, col, num))
		ans[arr[row][col] + 1]++;
	else {
		int newNum = num / 3;
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
				divide(row + newNum * i, col + newNum * j, newNum);
	}
}

int main() {
	ios_base::sync_with_stdio;
	cin.tie(0);
	cout.tie(0);
    
	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> arr[i][j];
    
	divide(0, 0, N);
    
	for (int i = 0; i < 3; i++)
		cout << ans[i] << '\n';
}

 

<시간 초과난 코드>

#include <iostream>
using namespace std;

int arr[2200][2200];
int num[3] = { 0, };
bool isSquare = true;
int first, Y;

void func(int n) {
	int a = n / 3;
	for (int i = 1; i <= n; i += a)
		for (int j = 1; j <= n; j++) {
			if (i%a == 1 && j%a == 1) {
				first = arr[i][j];
				Y = j;
				isSquare = true;
			}
			if (!isSquare)
				continue;
			for (int x = 0; x < a; x++)
				if (arr[i + x][j] != first) {
					if (n / 9 == 1) {
						for (int x = i; x < i + 3; x++) {
							for (int y = Y; y < Y + 3; y++)
								num[arr[x][y] + 1] += 1;
						}
						isSquare = false;
						break;
					}
					else
						func(n / 9);
				}
			if (j%a == 0 && isSquare)
				num[first + 1] += 1;
		}
	return;
}

int main() {
	int N;	
	cin >> N;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> arr[i][j];
	func(N);
	for (int i = 0; i < 3; i++)
		cout << num[i] << '\n';
}