Baekjoon1780-종이의 개수

백준 사이트 1780 - 종이의 개수 문제입니다.

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

분할정복 문제입니다.
재귀를 많이 사용하지 않아 뇌가 굳어버린 저는 어려웠습니다.
다른 사람의 코드를 참고하여 작성하였습니다.
백준에서는 sliver2 난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 솔직히 무슨 말 하는지는 알겠는데 코드로 그려지지가 않았다.

---

5. code

#include<iostream>

using namespace std;

int MAP[2200][2200];
int n;
int result[3] = { 0,0,0 };
void Input()
{
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
			cin >> MAP[i][j];
	}
}
bool check(int i, int j,int size)
{
	int start = MAP[i][j];
	for (int row = i; row < i + size; ++row)
	{
		for (int col = j; col < j + size; ++col)
		{
			if (start != MAP[row][col])
				return false;
		}
	}
	return true;
}

void divide(int i, int j,int size)
{
	//MAP[i][j]+1 을 해주는 이유는 -1이 들어왔을 경우 0으로 바꿔줘야함. -1인덱스는 없으므로.
	if (check(i, j, size))
		result[MAP[i][j] + 1]++;
	else
	{
		int div = size / 3;
		for (int row = 0; row < 3; ++row)
		{
			for (int col = 0; col < 3; ++col)
				divide(i + row * div, j + col * div, div);
		}
	}
}

void Solve()
{
	divide(0, 0,n);
	cout << result[0] << '\n' << result[1] << '\n' << result[2] << '\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	Input();
	Solve();
	return 0;
}

---

6. 후기

분할정복 어렵다.