04.04. 종이의 개수[Divide and conquer][백준 1780]

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

1780번: 종이의 개수

 

Algorithm classification : Divide and conquer, Recursion

 

04.04.1. Problem

There is a paper that is represented as a matrix of size N×N. Each cell on the paper contains one of -1, 0, or 1. We try to crop this matrix to the appropriate size according to the following rules.

 

1. If all the papers have the same number, use this paper as it is.
2. If it is not (1), cut the paper into 9 pieces of the same size and repeat the process of (1) for each cut paper.

 

Write a program that counts the number of papers filled only with -1, the number of papers filled with only 0s, and the number of papers filled with only 1s when the paper is cut like this.

 

04.04.2. Input limit

In the first line, N (1 ≤ N ≤ 3^7, N is given in the form of 3^k). The next N lines are given a matrix of N integers.

 

04.04.3. Output

Prints the number of papers filled only with -1 in the first line, the number of papers filled only with zeros in the second line, and the number of papers filled only with 1 in the third line.

 

04.04.4. Solution

항상 분할정복과 같은 문제를 풀 때, base case가 무엇인지 생각하셔야 합니다.(그냥 recursive function을 사용한다면 무조건이죠,) 정복하는 과정은 분할된 영역의 답을 더하는 계산만 하면 됩니다. Master theorem에서 a = 9, b = 9, d = 1이니가 O(NlogN)이 시간복잡도가 됩니다. N의 최대값과 시간제한이 2s라는 것을 고려하면 괜찮은 시간복잡도입니다.

void cal(int c_x, int c_y, int size){
	c = 0;
	if(size == 1){
		result[datab[c_x][c_y] + 1]++;
		return;
	}
	for(i = c_x - size/2; i <= c_x + size/2; i++){
		for(j = c_y - size/2; j <= c_y + size/2; j++){
			if(datab[c_x][c_y] != datab[i][j]){
				c++;
			}
		}
	}
	if(c==0){
		result[datab[c_x][c_y] + 1]++;
		return;
	}
	cal(c_x-size/3, c_y-size/3, size/3);
	cal(c_x-size/3, c_y, size/3);
	cal(c_x-size/3, c_y+size/3, size/3);
	cal(c_x, c_y-size/3, size/3);
	cal(c_x, c_y, size/3);
	cal(c_x, c_y+size/3, size/3);
	cal(c_x+size/3, c_y-size/3, size/3);
	cal(c_x+size/3, c_y, size/3);
	cal(c_x+size/3, c_y+size/3, size/3);
}

 

위의 code에서 저는 int result[3] = {0}; 배열을 사용하였는데요. 이렇게 처리한 이유는 if문으로 처리하는 것보다 훨씬 편하기 때문입니다. 어차피 datab의 값이 -1, 0, 1이니까 이것을 이용한 것입니다.

	cal(n/2+1, n/2+1, n);
	printf("%d\n%d\n%d\n", result[0], result[1], result[2]);