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

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

 

분할정복(divide and conquer) 문제입니다. 문제에 나와있는 그대로 풀면 됩니다. 종이가 다 같은 수로 되어 있으면 1장이고, 아니면 9등분을 합니다.

여기서 종이가 전부 같은 수로 되어있는지 체크를 어떻게 해야할지 좀 생각해봐야 합니다.

여러 방법이 있겠는데

• (0) (naive) 해당되는 칸을 전부 읽어봐서 같은지 확인한다
• (1) row-major order로 쭉 읽다가 동일하지 않은 숫자가 나오면 9등분
• (2) 재귀적으로 적당히 판별한다 (?) 

이 방법들은 아래에서 코드와 함께 설명하겠습니다

 

#include <bits/stdc++.h>
using namespace std;

int paper[2187][2187];
int cnt[3];	//-1, 0, 1

void cut(int y, int x, int side) {
	if (side == 1) {
		++cnt[paper[y][x]+1];
		return;
	}
	
	int first = paper[y][x];
	for (int i = y; i < y + side; ++i) {
		for (int j = x; j < x + side; ++j) {
			if (paper[i][j] != first) {
				int n = side / 3;

				cut(y, x, n);
				cut(y+n, x, n);
				cut(y+n+n, x, n);
				cut(y, x+n, n);
				cut(y+n, x+n, n);
				cut(y+n+n, x+n, n);
				cut(y, x+n+n, n);
				cut(y+n, x+n+n, n);
				cut(y+n+n, x+n+n, n);

				return;
			}
		}
	}

	++cnt[first + 1];
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;
	
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			cin >> paper[i][j];

	cut(0, 0, n);

	for (int i = 0; i < 3; ++i)
		cout << cnt[i] << '\n';

	return 0;
}

(1)번 방법을 구현한 소스입니다.

되게 직관적입니다. 하지만 row-major order로 배열 한 칸을 여러번 방문해야 하는 경우가 생깁니다.

그래서 좀 머리를 써서 '어떻게 해야 배열 한 칸에 여러번 접근을 안할까' 생각을 해봤는데 함수 return 값을 이용해서 적당히 판별하면 될 것 같아 다른 버전을 짜봤습니다.

 

int cut(int y, int x, int side) {
	if (side == 1) {
		++cnt[paper[y][x]+1];
		return paper[y][x];
	}

	int offset = side / 3;
	
	vector<int> colors(4);	//-1, 0, 1, NOT_SAME
	for (int i = 0; i < 3; ++i)
		for (int j = 0; j < 3; ++j)
			++colors[cut(y + offset*i, x + offset*j, offset) + 1];

	if (colors[0]==9 || colors[1]==9 || colors[2]==9) {
		cnt[paper[y][x] + 1] -= 8;
		return paper[y][x];
	}
	else {
		return NOT_SAME;
	}
}

(2)번 방법을 구현한 소스입니다

대략적인 설명은, 모든 1x1 사이즈 칸의 -1, 0, 1 개수를 다 세고, 3x3으로 합쳐지면 9장 -> 1장으로 되니 -8을 해줍니다. 3x3 -> 9x9로 되는 경우에도 -8을 해줍니다. 이런식으로 착착 합쳐줍니다.

함수 return값은 [y, x] ~ [y+sz, x+sz]까지의 범위의 배열값이 다 같으면 그 배열값을, 중간에 다른 칸이 있으면 NOT_SAME(#define NOT_SAME 2)를 반환합니다

각 함수에서는 종이를 9등분한 뒤 호출한 재귀호출의 반환값을 이용해 현재 종이가 온전한 한장인지 체크합니다.

 

쓰고 나니까 너무 복잡하네요. 그리고 1번보다 빠를 줄 알았는데.. 제출해보니 수행시간이 똑같습니다;

원인은 뭘까요. 종이에서 큰 부분이 많아지는 경우 (1)번은 큰 부분을 빠르게 잘라낼 수 있는데, (2)번은 그게 안되기 때문에 그런게 아닐까. 뭐 모르겠습니다 ;;