04.07. 별 찍기 - 10[Divide and conquer][백준 2447]

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

2447번: 별 찍기 - 10

 

Algorithm classification : Divide and conquer, Recursion

 

04.07.1. Problem

Let's take a star in a recursive pattern. If N is a power of 3 (3, 9, 27, ...), then the pattern of size N is N×N square. A size 3 pattern has a space in the center and a star in every cell except the center.

 

When N is greater than 3, the pattern of size N is a form in which a (N/3)×(N/3) square in the center filled with blanks is surrounded by a pattern of size N/3. For example, a pattern of size 27 is the same as example output 1.

 

04.07.2. Input limit

N is given in the first line. N is a power of 3. That is, for some integer k, N=3^k, where 1 ≤ k < 8.

 

04.07.3. Output

Prints a star from the first line to the Nth line.

 

04.07.4. Solution

이 문제는 학부과목에서 과제나 예시로 반드시 나오는 유형입니다. 

char a[6561][6561] = {0};

void cal(int c_x, int c_y, int size){
	if(size == 1)	return;
	//printf("%d %d %d\n", c_x, c_y, size);
	for(i = c_x + size/3; i < c_x + size/3*2; i++){
		for(j = c_y + size/3; j < c_y + size/3*2; j++){
			a[i][j] = 'a';
		}
	}
	cal(c_x, c_y, size/3);
	cal(c_x, c_y + size/3, size/3);
	cal(c_x, c_y + size/3*2, 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 + size/3, c_y + size/3*2, size/3);
	cal(c_x + size/3*2, c_y, size/3);
	cal(c_x + size/3*2, c_y + size/3, size/3);
	cal(c_x + size/3*2, c_y + size/3*2, size/3);
}

뭐, 크게 다른 방법이 나올수 없는 문제이긴 합니다. 다만 센스를 조금 볼 수 있는데, 전역변수로 배열을 선언해두고 각 칸을 채우는 것이 효율적입니다. 또한 배열의 자료형을 굳이 int로 둘 필요없이 char로 하면 조금 더 절약할 수 있겠죠. 기저 Case를 size = 1로 두셔도 되고 size = 3으로 두셔도 됩니다. 정서상 size = 1이 편해보이긴 합니다.

 

	cal(1, 1, n);
	for(i = 1; i <= n; i++){
		for(j = 1; j <= n; j++){
			printf("%c",a[i][j] ? ' ' : '*');
		}
		printf("\n");
	}