[백준 2630] 색종이 만들기

난이도

실버 II

📜문제

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

🔎접근

같은 행동을 반복적으로 하기 때문에 분할 정복으로 접근을 할 수 있다. 반복이 될 함수에 시작 좌표(x,y)를 넣어주고 몇번 반복할건지를 정하기 위해 size를 넣어준다.

🌞풀이

#include <iostream>

using namespace std;

bool matrix[128][128];
int white, blue = 0;

void Calculate(int size, int x, int y)
{
    //함수 종료 조건
	if (size == 1)
	{
		if (matrix[x][y] == 1) blue++;
		else white++;
		return;
	}

	bool onlyOne = true;
	bool onlyZero = true;

	for (int i = x; i < x + size; i++)
	{
		for (int j = y; j < y + size; j++)
		{
			if(matrix[i][j] == 0) onlyOne = false;
			if(matrix[i][j] == 1) onlyZero = false;
		}
	}

	if (onlyZero)
	{
		white++;
		return;
	}
	if (onlyOne)
	{
		blue++;
		return;
	}

    // 재귀
	Calculate(size / 2, x, y);
	Calculate(size / 2, x + size / 2, y);
	Calculate(size / 2, x, y + size / 2);
	Calculate(size / 2, x + size / 2, y + size / 2);
}

int main()
{
	int N = 0;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >>matrix[i][j];
		}
	}

	Calculate(N, 0, 0);

	cout << white << "\n" << blue << "\n";

	return 0;
}

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기