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

문제

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

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

*** * * ***

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

입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

 

<코드>

#include<iostream>
#include<cmath>
using namespace std;

int N;
bool flag;

int main() 
{
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			flag = false;
			for (int k = N; k > 1; k = k / 3)
			{
				if (i % k >= (k / 3) && i % k < (k / 3) * 2)
					if (j % k >= (k / 3) && j % k < (k / 3) * 2)
					{
						flag = true;
						break;
					}
						
			}
			if (flag == true) cout << " ";
			else cout << "*";
		}
		cout << '\n';
	}
}

 

풀이 방법

입력이 N이라면 NxN 크기의 별이 출력됩니다.

먼저 bool형의 flag변수를 두고 각각의 좌표를 N/3으로 나눌 때의 나머지가 둘 다 N/3 이상 (N/3) * 2 미만일 경우 flag를 true로 바꿔주고 반복문을 break 해줍니다. 별이나 공백을 출력하면 N = N / 3을 해주어 N이 3 될 때까지 반복합니다.

 예를 들자면 입력이 27이라고 할 때,

1. 각각의 좌표를 27/3 = 9로 나눴을 때 나머지 둘 다 27/3 = 9 이상 (27/3) * 2 = 18 미만인 좌표들은
   모두 flag를 true로 바꿔줍니다. 
2. 27/3을 해준 다음 위의 과정을 다시 반복하면!
3. 각각의 좌표를 9/3 = 3로 나눴을 때 나머지 둘 다 9/3 = 3 이상 (9/3) * 2 = 6 미만인 좌표들은
   모두 flag를 true로 바꿔줍니다. 
4. 이런 식으로 k가 3이 될 때까지 반복하며, 중간중간에 flag가 true 될 때 공백을 출력하고 반복문을 탈출하여
   다음 좌표로 넘어갑니다.
5. 반복문이 종료됐을 때 flag값이 false라면 별을 출력하고 다음 좌표로 넘어갑니다.

 

 

<재귀 함수를 통한 더 간결한 풀이>

#include<iostream>
#include<cmath>
using namespace std;

int N;

void star(int x, int y, int n)
{
	if ((x / n) % 3 == 1 && (y / n) % 3 == 1) cout << " ";
	else
	{
		if (n == 1) cout << "*";
		else star(x, y, n / 3);
	}
}

int main()
{
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			star(i, j, N/3);
		cout << '\n';
	}
}

 

풀이 방법

입력이 27이라고 할 때 모든 좌표들을 n = 9으로 나눠주면

여기서 위의 값에서 3으로 나눴을 때 둘 다 나머지가 1인 것(빨간 사각형)들은 모두 공백 처리를 해준다.

 

그리고 다시 모든 좌표를 n = 3으로 나눠주면

여기서 위의 값에서 3으로 나눴을 때 둘다 나머지가 1인 것(빨간 사각형)들은 모두 공백처리를 해준다.

 

그리고 n = 1일 때 모든 좌표를 1로 나눠준 후

여기서 위의 값에서 3으로 나눴을 때 둘 다 나머지가 1인 것(빨간 사각형)들은 모두 공백 처리를 해준다.

fractal 구조 완성.

 

 

ps. 1년전에 하노이탑이랑 이 문제를 처음 접했을 때는 정답 코드를 봐도 이해가 안가고 너무 어려웠었는데 알고리즘 공부하면 할 수록 실력이 느는게 보이는것 같다. 

 

 

www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10