[백준 2448번] 별 찍기 - 11 (C++)

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

2448번: 별 찍기 - 11

 

이미지 예시

재귀가 3번 반복되므로 시간복잡도가 O(n의 log2 3승)이다. 잘못하면 시간초과가 날 수 있으므로 연산량을 최대한 줄이는 것이 좋다.

#include<iostream>

using namespace std;
int map[6143][3702];

void fractal(int size, int x, int y) {
	if (size == 1) return;
	if (size == 3) {
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 5; j++) {
				if (i == 2 && j == 2) map[x+j][y+i] = 1;
				if (i == 1 && j % 2) map[x+j][y+i] = 1;
				if (i == 0) map[x+j][y+i] = 1;

			}
		}
		
	}
	int newSiz = size >> 1;
	fractal(newSiz, x, y);
	fractal(newSiz, x + size, y);
	fractal(newSiz, x + newSiz, y + newSiz);
}

int main(void) {
	int N;
	cin >> N;
	fractal(N, 0, 0);
	for (int i = N-1; i >=0; i--, cout << "\n") {
		for (int j = 0; j < 2 * N - 1; j++) {
			if (map[j][i]) cout << "*";
			else cout << " ";
		}
	}
	return 0;
}