문제

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

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

***
* *
***

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

문제풀이

사용한 알고리즘 : 구현

문제 조건에 따라 별 찍기를 string으로 리턴하는 재귀 함수를 구현해주었습니다.

K=1 일때 "*" 이라고 기저를 설정해 주었습니다.

이후 NxN 크기의 별찍기를 하는 방법은 다음과 같습니다.

1. 재귀를 통해 이전 단계 별 찍기를 마련해 놓는다.

2. 이번 단계를 만들 때, 중앙 부분은 비워준다.

3. 중앙이 아닌 경우 해당 위치를 모듈러 쳐서 만들어 놓은 이전 단계에서 해당부분을 찾아 붙인다.

N개씩 행으로 잘라서 출력해줍니다.

	#include<bits/stdc++.h>
	using namespace std;

	int N;

	string path(int k) {
	if (k == 1) return "*"; // 기저

	string ret;
	string pre = path(k / 3); // 바로 전 단계의 별 찍기
	int s = k / 3; // 전 단계의 한 변의 크기 (전 단계는 k/3 * k/3 크기이다)
	// 이번거 만들기
	for (int i = 0; i < k; ++i) { // 행
	for (int j = 0; j < k; ++j) { // 열
	// 중앙은 뚫기
	if (i >= s && i < 2 * s && j >= s && j < 2 * s) ret += ' ';
	// 중앙이 아니면
	else {
	// 모듈러 쳐서
	int x = i % s;
	int y = j % s;
	// 이전꺼에서 해당 부분 찾아 붙이기
	ret += pre[x * s + y];
	}
	}
	}

	return ret;
	}

	int main() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N;
	string ans = path(N);
	for (int i = 0; i < ans.size(); ++i) {
	if (i != 0 && i % N == 0) cout << '\n';
	cout << ans[i];
	}

	return 0;
	}

view raw BOJ 2447.cpp hosted with ❤ by GitHub