별 찍기 - 10 C++ - 백준 2447

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

재귀를 사용한 별 찍기 문제.

문제 접근

1. 구상

$3\cdot3$ 형태를 가장 기본 형태로 취해 string vector의 행에 하나씩 넣는 방식을 채택.

2. 구현

$3^k$ 꼴의 모양이 출력된 후 행의 조정이 필요하다.

예를 들어 $n=9$일때는,

$n=3$인 모양을 3번 처리하고 인덱스를 3 늘려주고 2번째 줄 3개 처리하고, 인덱스 3 늘려주는

방식으로 진행된다.

$3^{k-1}$을 9개 출력해야 된다고 했을 때 위 과정을 한번 진행하고는 인덱스를 다시

0으로 만들어주어야 한다.

따라서 $n=3^k$ 일때는 $3^{k-1}$ 하나 돌리고 인덱스를 $3^{k-1}$만큼 줄여준다.

이를 구현한 코드는 다음과 같다.

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

vector<string> ans[2188];
int ck=0;

void solve(int n, bool b){
	if(n==3 && b){
		ans[ck+1].push_back("* *");
		for(int i=0;i<3;i+=2) ans[ck+i].push_back("***");
		return;
	}
	if(!b){
		string s("");
		for(int i=0;i<n;i++) s+=' ';
		for(int i=0;i<n;i++) ans[ck+i].push_back(s);
		return;
	}
    if(n!=9){
		for(int j=0;j<4;j++){
			solve(n/3,1); if(j!=2) ck-=n/3;
		}
		solve(n/3,0);
		for(int j=0;j<3;j++){
			solve(n/3,1); if(j!=0) ck-=n/3;
		}
		solve(n/3,1);
    }
    else{
    	for(int j=0;j<3;j++) solve(3,1);
    	ck+=3;
    	solve(3,1);
    	solve(3,0);
    	solve(3,1);
    	ck+=3;
    	for(int j=0;j<3;j++) solve(3,1);
    	ck+=3;
    }
    return;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n; cin >> n;
	solve(n,1);
	for(int i=0;i<n;i++){for(string c:ans[i]){cout << c;} cout << '\n';}
	return 0;
}