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

이 문제는 구현 문제이다.

 

규칙성을 찾아내는 것이 가장 중요한 포인트이다.

N이 주어졌을 때 가로의 길이는 N번째 홀수와 같다. 따라서 2 * N - 1이 된다.

또한 높이가 주어졌을 때 높이 / 2 한 부분에서 2개의 삼각형이 나오게 된다. 또한 각 2개의 삼각형의 x좌표는 각각 x - height / 2, x + height / 2가 된다.

 

이러한 규칙성을 찾았다면 재귀를 통해 구현하고, 높이가 3일 때를 base case로 잡아 문제를 해결할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<vector<char>> output;

void draw(int y, int x, int height) {
	if (height == 3) {
		output[y][x] = '*';
		output[y + 1][x - 1] = '*';
		output[y + 1][x + 1] = '*';
		for (int i = x - 2; i <= x + 2; i++) {
			output[y + 2][i] = '*';
		}
		return;
	}

	int width = 2 * height - 1;
	draw(y, x, height / 2);
	// left
	draw(y + height / 2, x - height / 2, height / 2);
	// right
	draw(y + height / 2, x + height / 2, height / 2);
}

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

	int N;
	cin >> N;

	output = vector<vector<char>>(N, vector<char>(2 * N - 1, ' '));
	int width = 2 * N - 1;
	draw(0, width / 2, N);

	int w = output[0].size();
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < w; x++) {
			cout << output[y][x];
		}
		cout << '\n';
	}
	
	return 0;
}