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

링크

---

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

문제

---

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

---

첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수)

출력

---

첫째 줄부터 N번째 줄까지 별을 출력한다.

풀이

---

별 찍기-10번 문제를 풀었다면 알고리즘을 구상하는데에 큰 어려움은 없을 것이다.

먼저 주의사항이 있는데 삼각형의 왼쪽 오른쪽 공백은 반드시 출력해야한다.
나는 이 공백들을 재귀가 시작되기전, 끝난후에 출력해줌으로써 해결하였다.

규칙을 찾을 때 헷갈리는 공백을 제거한 삼각형의 모양을 보면 다음과 같다.

여기서 규칙을 찾아보면 다음과 같다.
1. 가운데 공백 삼각형과 나머지 삼각형으로 나눌 수 있다.
2. 가운데 삼각형을 제외한 나머지 삼각형들은 서로 모양이 같다.

따라서 재귀를 실행할 때 가운데 삼각형이 아니라면 좌표값을 조정하고 크기를 1/3로 줄인 후
위쪽 삼각형을 기준으로 다시 재귀를 실행한다.

또한 제일 작은 삼각형인 N=3일 때의 최소값 조건문을 넣어준다.

코드

---

#include <iostream>
using namespace std;

void recurse(int x, int y, int size) {
	if (size == 3) {
		if (x == 1 && y == 1)
			cout << " ";
		else
			cout << "*";
		return;
	}
	else {
		if (x >= size / 2 && y > (x - size / 2) * 2 && y < size) {
			cout << " ";
			return;
		}
		else if (x < size / 2) {
			recurse(x, y, size / 2);
		}
		else if (y <= (x - size / 2) * 2) {
			recurse(x - size / 2, y, size / 2);
		}
		else if (y >= size) {
			recurse(x - size / 2, y - size, size / 2);
		}
	}

	return;
}

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

	for (int i = 0; i < N; i++) {
		for (int k = N - i - 1; k > 0; k--) {
			cout << " ";
		}
		for (int j = 0; j < 2 * i + 1; j++) {
			recurse(i, j, N);
		}
		for (int k = N - i - 1; k > 0; k--) {
			cout << " ";
		}
		cout << "\n";
	}

	return 0;
}