[백준] 10993번: 별 찍기 - 18

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

10993번: 별 찍기 - 18

재밌어보여서 풀기 시작했다가 복잡해서 당황했다..;;

출력 삼각형을 잘 관찰해보면 가장 큰 삼각형 안에 이전 수준의 삼각형이 있고, 또 그 안에 이전 수준의 삼각형이 있고... 를 반복하는 것을 알 수 있다.

삼각형의 크기는 이전 수준의 삼각형의 대략 2배정도이므로 지수승으로 커진다.

 

이 점을 이용해서 top-down(재귀) 방식이나 bottom-up(for문) 방식으로 풀면 되는데 나는 for문으로 풀었다.

 

한줄짜리 string을 저장하는 덱을 선언한 뒤,

가장 작은 삼각형부터 덱에 넣는다.

그리고 그보다 한단계 큰 삼각형을 추가하고 추가하고... 하는 방식으로 풀면 된다.

 

star랑 space는 그냥 개수를 입력받아서 그 개수만큼 별이나 공백을 반환해주는 함수이다.

 

시간이 많이 걸린 문젠데 막상 풀고 나니 로직이 그렇게 복잡하진 않은 것 같다.

for문으로 돌 공백 개수만 잘 계산해주면 될 듯!

사실 재귀로 푸는 것이 더 편할거 같다는 생각이 든다.

 

#include <iostream>
#include <string>
#include <cmath>
#include <deque>
using namespace std;

deque<string> shape;

string star(int a) {
	string result;
	for (int i = 0; i < a; i++) result += "*";
	return result;
}

string space(int a) {
	string result;
	for (int i = 0; i < a; i++) result += " ";
	return result;
}

void draw(int size) {
	if (size % 2 == 0) {
		// 아랫부분
		for (int i = 0; i < shape.size(); i++) {
			string result;
			result += "*";
			result += space(i * 2);
			result += shape[i];
			result += space(i * 2);
			result += "*";
			shape[i] = result;
		}

		shape.push_back(star(pow(2, size + 2) - 3));

		//위쪽 삼각형
		for (int i = pow(2, size) - 2; i > 0; i--) {
			string result;
			result += "*";
			result += space(i * 2 - 1);
			result += "*";
			shape.push_front(result);
		}
		shape.push_front("*");
	}

	if (size % 2 == 1) {
		// 윗부분
		for (int i = 0; i < shape.size(); i++) {
			string result;
			result += "*";
			result += space((shape.size() - i - 1) * 2);
			result += shape[i];
			result += space((shape.size() - i - 1) * 2);
			result += "*";
			shape[i] = result;
		}

		shape.push_front(star(pow(2, size + 2) - 3));

		//아래쪽 삼각형
		for (int i = pow(2, size) - 2; i > 0; i--) {
			string result;
			result += "*";
			result += space(i * 2 - 1);
			result += "*";
			shape.push_back(result);
		}
		shape.push_back("*");
	}
}

int main() {
	int n;
	scanf("%d", &n);

	shape.push_back("*");

	for (int i = 1; i < n; i++) {
		draw(i);
	}

	if (n % 2 == 1) {
		for (int i = 0; i < shape.size(); i++) {
			cout << space(shape.size() - 1 - i);
			cout << shape[i] << "\n";
		}
	}

	if (n % 2 == 0) {
		for (int i = 0; i < shape.size(); i++) {
			cout << space(i);
			cout << shape[i] << "\n";
		}
	}
}