[C++] 별 찍기 - 10 : 2447번

문제

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***
* *
***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

---

해석

재귀적으로 생각이 안나서 혼자 해결하지 못했다.

 

[백준 / BOJ] - 2447번 별 찍기 -10 C++ 풀이 :: Just Give Me The Code (tistory.com)

[백준 / BOJ] - 2447번 별 찍기 -10 C++ 풀이

이곳을 참고했다.

규칙을 찾기 위해 엑셀을 사용하여 N = 27 일 때를 그려보았다.

(1, 1) (1, 4) (1, 7) ... >>  x % 3 == 1

(3, 3) (3, 4) ... (5, 5) >> x / N / 3 / 3 % 3 == 1

(9, 9) (9, 10) ... (17, 17) >> x / N / 3 % 3 == 1

 

x 를 N 을 n번 쪼갠 수로 나누었을 때 몫이 1이 되면 공백의 자리가 된다.

이 규칙을 찾기가 많이 어려웠다고 생각한다.

또 이 규칙을 재귀적으로 바꾸는 것도 어려웠다.

 

N을 n 번 쪼개는 것은 재귀호출을 하면서 N / 3 을 매개변수로 전달하며 쪼갤 수 있다.

 

코드

#include <iostream>
using namespace std;

void MakeStar(int i, int j, int N);

int main()
{
	int N; // 수 입력
	cin >> N;
	
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			MakeStar(i, j, N);
		}
		cout << "\n";
	}
	return 0;
}

void MakeStar(int i, int j, int N)
{
	if ((i / N) % 3 == 1 && (j / N) % 3 == 1) // 공백이 되기 위한 조건 : 
	{																// 3으로 나눈 나머지가 1이면 공백자리
		cout << " ";
	}
	else // 공백 자리가 아니면
	{
		if (N / 3 == 0) // 나누는 다음 N 이 0이 되면 가능성이 없으므로 종료
		{
			cout << "*";
			return;
		}
		else 	MakeStar(i, j, N / 3); // 다음 N / 3 으로 공백인지 검사
	}
}