BOJ 백준 1780 : 종이의 개수

시작하면서

이번 문제는 분할 정복 카테고리 문제이다.

BOJ 1780 - 종이의 개수

​

개념

간단하게나마 살펴보겠다.

​

1. 분할 정복 (Divide and Conquer)
   • 개념
   • 분할 정복은 기본적으로 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발했다. 대표적으로는 퀵소트와 합병 정렬이 있다.
   • 장점
     • 문제를 나눔으로써 어려운 문제를 해결할 수 있다. 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결하는 데 큰 강점이 있다.
   • 단점
     • 함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 발생하며, 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게 되는 단점이 있다.

​

문제 이해

문제를 읽어보자. 먼저 이 문제에서 나오는 변수의 종류는 총 1가지이다.

• N ( 1<= N <= 3^7) : 종이의 수가 되는 줄의 수
• 종이에 그려진 수 : -1 , 0, 1

이 변수를 가지고 답을 출력해야한다. 이 문제는 예제를 이해하기 쉬우니 예제 읽기는 생략한다.

​

문제 아이디어

내 아이디어는 다음과 같다.

1) 현재 종이의 첫 번째 숫자와 다른 숫자들을 비교한다.

2) [규칙 1]에 의해 종이의 숫자가 하나라도 다르면 종이를 잘라야하니, 종이에 있는 모든 숫자를 비교해야만 한다.

3-1) 이 문제를 풀기 위해서는 [규칙 2]의 행동을 ‘반복’하므로, 재귀를 사용할 것이다. 3-2) 가장 큰 경우의 수는 ‘3^7’이다. 이때 종이는 가로x세로 이므로 최대로 재귀를 해도 14번이다. (혹시 아니라면 댓글 부탁드립니다) 스택 오버플로우는 일어나지 않을 것이다.

​

해결

위 아이디어로 다음과 같이 해결했다.

#include <iostream>

using namespace std;

// function
void InputN();
void InputArray();
void SolveProblem();
void PrintAnswer();
void CheckPaper(int x, int y, int nowN);
void CutPaper(int x, int y, int nowN);

// variable
int N = 0;
int answer[3] = { 0, };
int inputArray[2188][2188] = { 0, };

int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);

	InputN();
	InputArray();
	SolveProblem();
	PrintAnswer();
}

// N
void InputN()
{	
	cin >> N;
}

// Array
void InputArray()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> inputArray[i][j];
		}
	}
}

// Solve
void SolveProblem()
{	
	CheckPaper(0, 0, N);
}

// Answer
void PrintAnswer()
{
	cout << answer[0] << "\n" << answer[1] << "\n" << answer[2] << "\n";
}

// 종이에 있는 숫자들이 모두 일치하는지 검사
void CheckPaper(int x, int y, int nowN)
{
	int standardNumber = inputArray[x][y];

	for (int i = x; i < x + nowN; i++)
	{
		for (int j = y; j < y + nowN; j++)
		{
			// 하나라도 일치하지 않으면 중지하고, 다시 자른다
			if (inputArray[i][j] != standardNumber)
			{
				CutPaper(x, y, nowN);
				return;
			}
		}
	}
	
	// 종이의 숫자가 모두 같으면 카운트를 올린다.
	answer[standardNumber + 1]++;
}

// 종이를 9등분으로 자른다
void CutPaper(int x, int y, int nowN)
{
	for (int a = 0; a < 3; a++)
	{
		for (int b = 0; b < 3; b++)
		{
			CheckPaper(x + a * (nowN / 3), y + b * (nowN / 3), nowN / 3);
		}
	}
}

​

​

마치며

오랜만에 문제 풀이여서 그런지 컴파일 에러도 많고, 귀찮음이 꽤 있었다. 그래도 알고리즘 푸는게 재밌음을 다시 느꼈다. 이 재미를 계속 느끼면서 공부해나가겠다.