[BOJ]1780번: 종이의 개수 (c++)

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

1780번: 종이의 개수

 

분할 정복

#include <iostream>
#include <vector>

using namespace std;

vector<int> nums;

struct pos {
	int x, y;
};

// strt부터 가로세로 len의 영역의 숫자가 모두 같은지 확인
bool same_num_area(vector<vector<int>> &paper, pos &strt, int len)
{
	int num = paper[strt.x][strt.y];
	for (int i = strt.x; i < strt.x + len; ++i)
	{
		for (int j =  strt.y; j < strt.y + len; ++j)
		{
			if (paper[i][j] != num)
			{
				return false;
			}
		}
	}
	return true;
}

void cut_paper(vector<vector<int>> &paper, pos strt, int len)
{
	/*
		strt부터 가로세로 len의 영역의 숫자가 모두 같으면
		: 해당 숫자개수 + 1
	*/
	if (same_num_area(paper, strt, len))
	{
		++nums[paper[strt.x][strt.y] + 1];
		return;
	}

	/*
		가로 세로를 9구간으로 나누어 
		각 구간의 첫번째 위치값과 구간 길이값으로 재귀호출
	*/
	for (int i = strt.x; i < strt.x + len; i += len / 3)
	{
		for (int j = strt.y; j < strt.y + len; j += len / 3)
		{
			cut_paper(paper, {i, j}, len / 3);
		}
	}
}

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

	// 입력
	int N;
	cin >> N;
	vector<vector<int>> paper(N, vector<int>(N));
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> paper[i][j];
		}
	}

	// 같은 숫자로만 채워진 (숫자별)종이개수 구하기
	nums = vector<int>(3);
	cut_paper(paper, {0, 0}, N);

	// 출력
	for (int n : nums)
	{
		cout << n << '\n';
	}

	return 0;
}

 

(1) 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
(2) (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

 

주어진 2차원배열을 계속해서 더 작은 단위의 벡터로 나누어가며 푸는 문제이다. 

 

사실 문제의 조건자체가 매우 재귀적이기 때문에,

시작점과 자르는 크기값(* 1/3배)만 잘 넘겨주면 된다. 

void cut_paper(vector<vector<int>> &paper, pos strt, int len)
{
	...
	
	/*
		가로 세로를 9구간으로 나누어 
		각 구간의 첫번째 위치값과 구간 길이값으로 재귀호출
	*/
	for (int i = strt.x; i < strt.x + len; i += len / 3)
	{
		for (int j = strt.y; j < strt.y + len; j += len / 3)
		{
			cut_paper(paper, {i, j}, len / 3);
		}
	}
}