[백준 C++] 2448 별 찍기 - 11 - 재귀

2448번: 별 찍기 - 11

#include <iostream>
using namespace std;

char Board[3072][6143];

void DrawTriangle(int N, int Row, int Col)
{
	if (N == 3)
	{
		for (int i = 0; i < N; ++i)
		{
			Board[Row + i][Col - i] = '*';
			Board[Row + i][Col + i] = '*';
		}

		for (int i = 0; i < 2; ++i)
		{
			Board[Row + N - 1][Col - i] = '*';
			Board[Row + N - 1][Col + i] = '*';
		}

		return;
	}

	DrawTriangle(N / 2, Row, Col);
	DrawTriangle(N / 2, Row + N / 2, Col - N / 2);
	DrawTriangle(N / 2, Row + N / 2, Col + N / 2);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int N;
	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < 2 * N - 1; ++j)
		{
			Board[i][j] = ' ';
		}
	}

	DrawTriangle(N, 0, N - 1);

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < 2 * N - 1; ++j)
		{
			cout << Board[i][j];
		}
		cout << '\n';
	}
}

---

 

재귀로 푸는 별찍기 문제입니다.

한 변의 크기가 큰 삼각형부터 크기가 3인 삼각형까지 내부로 쪼개서 들어간다음

크기가 3인 삼각형을 모두 그려주면 됩니다.

풀이 과정은 다음과 같습니다.

 

* 하나의 삼각형은 한 변의 크기와 위쪽 꼭지점의 위치(행, 열)로 정의

1. 큰 삼각형은 세 개의 작은 내부 삼각형으로 쪼개져서 재귀 함수 호출

1-a. 큰 삼각형의 한 변의 길이(N), 위치(Row, Col)

1-b. 위쪽 내부 삼각형의 한 변의 길이(N/2), 위치(Row, Col)

1-c. 아래 왼쪽 삼각형의 한 변의 길이(N/2), 위치 (Row + N/2, Col - N/2)

1-d. 아래 왼쪽 삼각형의 한 변의 길이(N/2), 위치 (Row + N/2, Col + N/2)

2. 현재 삼각형의 길이(N)이 3이 되면 삼각형을 배열에 저장하고 재귀 탈출

3. 저장된 배열 출력