[2448] 별 찍기 - 11

---

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

2448번: 별 찍기 - 11

재귀 문제이다.

 

4시간동안 삽질하다가 풀었다.

비어있는 공간을 중심으로 코드를 짜보기도 하고, '*'을 중심으로 코드를 짜보기도 했는데, 결국은 다 구현하지 못했다.

 

 

최후의 방법은 삼각형 맨 위의 꼭짓점의 좌표 정보를 담고 재귀를 진행하는 것이었다.

말보다는 그림이 더 편할 것 같다!

삼각형 맨 위의 꼭짓점에서 위쪽/왼쪽/오른쪽의 삼각형이 다시 재귀함수로 들어간다.

이 역시 맨 위의 꼭짓점 좌표 정보가 들어간다.

 

파란색 동글 -> 하늘색 동글 이런식으로 파고들다가 특정 조건이 되면 배열에 '*'를 담는다.

 

 

말로 설명하기 힘들어서 코드로 대체한다..

#include <iostream>
using namespace std;

int N;
char A[3072][6143];

void star(int x, int y, int exponent) {
	if (exponent < 1) {
		A[y][x] = '*';
		A[y + 1][x - 1] = '*'; A[y + 1][x + 1] = '*';
		for (int i = x - 2; i <= x + 2; i++) A[y + 2][i] = '*';
		return;
	}
	int p = 1; exponent--; // 지수 감소
	for (int i = 0; i < exponent; i++) {
		p = p << 1; // 2^exponent를 p에 저장
	}
	star(x, y, exponent); // 위
	star(x - 3 * p, y + 3 * p, exponent); // 왼쪽
	star(x + 3 * p, y + 3 * p, exponent); // 오른쪽
}

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

	cin >> N;
	
	int a = N / 3;
	int q = 1;
	for (int i = 0;; i++) {
		if (q == a) { a = i; break; }
		q = q << 1; // 2배
	}
	star(N - 1, 0, a);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 2 * N - 1; j++) {
			if (A[i][j] == '*') printf("*");
			else printf(" ");
		}
		printf("\n");
	}
}