[BAEKJOON] 2448번 별 찍기 - 11

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

2448번: 별 찍기 - 11

예시 그림

이 문제의 핵심은 이 그림을 가지고 어떤 규칙이 있는지 유추하는 것이 핵심이다.

같은 모양이 반복적으로  나타나는 구조인 프랙탈(?) 구조인 것을 볼 수 있다.

여기서 나의 접근 방법은 Top-Down Approach를 통 DFS로 결정을 했다.

3x2^k (0<=k<=10) 인 줄까지 출력을 해야하는데 여기서

 

이 모양이 가장 기본이 되는(가장 작은) 별 모양이다.

나는 이것을 하나의 '그룹' 이라고 정했다. 

 

 

점화식

 맨 왼쪽위의 좌표를 (y,x) 라고 두었을때의 점화식을 표현했다.

그리고 각 그룹의 제일 왼쪽이고 위쪽인 좌표를 기준으로 두었다.

그림만 잘 해석해서 점화식만 잘 세워준다면 어려울 것 없는 문제였다,,(문제는 그림 해석이 진짜 오래걸렸다는 점이지만,,,)

소스코드

#include <vector>
#include <iostream>
#include <string>
#define MAX 3100
using namespace std;
int n;
string star[] = {"  *  ", " * * ", "*****"};
char map[MAX][MAX*2];
//규칙적인 별 모양이 3x2^k 만들어 지고, 크게 세부분으로 나눠짐
void dfs(int num, int y, int x) {
	if (num == 1) {
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 5; j++) map[y + i][x + j] = star[i][j];
		return;
	}
	dfs(num / 2, y, x+3*num/2);
	dfs(num / 2, y + 3 * num / 2, x);
	dfs(num / 2, y + 3 * num / 2, x + 3 * num);
}
int main() {
	cin >> n;
	dfs(n / 3, 0, 0);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 2 * n - 1; j++) {
			if (map[i][j] == '*') cout << '*';
			else cout << ' ';
		}
		cout << '\n';
	}
}