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

2448번: 별 찍기 - 11

cpp

#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. 저장된 배열 출력