[백준 10993] 별 찍기 - 18

문제 링크 : 10993번: 별 찍기 - 18 (acmicpc.net)

10993번: 별 찍기 - 18

문제

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

입력

첫째 줄에 N(1 ≤ N ≤ 10)이 주어진다.

출력

첫째 줄부터 차례대로 별을 출력한다.

예제 입력 1 복사

1

예제 출력 1 복사

*

예제 입력 2 복사

2

예제 출력 2 복사

*****
 ***
  *

예제 입력 3 복사

3

예제 출력 3 복사

      *
     * *
    *   *
   *******
  *  ***  *
 *    *    *
*************

예제 입력 4 복사

4

예제 출력 4 복사

*****************************
 *            *            *
  *          * *          *
   *        *   *        *
    *      *******      *
     *    *  ***  *    *
      *  *    *    *  *
       ***************
        *           *
         *         *
          *       *
           *     *
            *   *
             * *
              *

 

---

 

재귀를 활용한 별 찍기 문제이다.

 

접근 방식은 다음과 같다.

1. 먼저 규칙성을 따져보도록 하자.

N이 짝수일때와 홀수일때로 구분할 수 있다.

(1) N이 짝수일 경우 : 정삼각형이 180도 회전된 상태

(2) N이 홀수일 경우 : 정삼각형 그대로의 상태

 

2. N에 해당하는 정삼각형 내부에 N - 1에 해당하는 정삼각형이 존재하는 것을 알 수 있다.

좀 더 일반화해서 생각하면 다음과 같이 생각할 수 있겠다.

 

 

3. 2번 방법을 좀 더 구체적으로 생각해보도록 하자.

여기서 별을 찍기 위해서 2차원 좌표로 생각해보도록 해보자.

 

 

기준점을 빨간색 점 (x, y) 로 하여 (x, y) 를 기준으로 n 에 대한 별을 채우고 n - 1 에 대한 별을 채우고 n - 2 에 대한 별을 채우는 방식임을 알 수 있다.

즉, 재귀적으로 n과 기준점 (x, y) 를 가지고 n이 짝수인지 홀수인지에 대한 구분만 할 수 있다면 별을 채울 수 있다는 것이 핵심이다.

 

그렇다면 별을 채우기 위해서 2차원 배열 char 형 Star 이 필요할 것이고 위에서 설명한 방식 그대로 별들을 채워가면 된다.

 

※ 주의 사항

N = 0 이 되는 순간 재귀적 호출이 중지되도록 리턴하는 것을 잊지 말자.

그리고 별의 가장 오른쪽 부분은 ' ' 빈칸으로 채워진 것이 아니기 때문에 이에 대한 처리를 꼭 해주도록 해야 한다.

즉, 별 가장 오른쪽 다음을 ' ' 프린트를 하는 것이 아니라 개행 처리를 해줘야 한다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <math.h>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

char Star[2100][2100];

void init_Star(int N) {
	int row = pow(2, N) - 1;
	int col = row * 2 - 1;
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			Star[i][j] = ' ';
		}
	}
}

void set_Star(int N_, int N, int x, int y) {
	if (N == 0)
		return;
	if (N % 2 == 0) {
		int gap = pow(2, N) - 1;
		for (int i = 0; i < gap; i++) {
			if (i == 0) {
				for (int j = 0; j < 2 * gap - 1; j++)
					Star[x + i][y + j] = '*';
			}
			else {
				Star[x + i][y + i] = Star[x + i][y + (2 * gap - 2 - i)] = '*';
				if (N_ == N) Star[x + i][y + (2 * gap - 1 - i)] = 'x';
			}
		}
		set_Star(N_, N - 1, x + 1, y + pow(2, N - 1));
	}
	else {
		int gap = pow(2, N) - 1;
		for (int i = 0; i < gap; i++) {
			if (i == gap - 1) {
				for (int j = 0; j < 2 * gap - 1; j++) {
					Star[x + i][y + j] = '*';
				}
			}
			else {
				Star[x + i][y + (gap - 1 - i)] = Star[x + i][y + (gap - 1 + i)] = '*';
				if (N_ == N) Star[x + i][y + (gap + i)] = 'x';
			}
		}
		set_Star(N_, N - 1, x + pow(2, N - 1) - 1, y + pow(2, N - 1));
	}
}

void show_Star(int N) {
	int row = pow(2, N) - 1;
	int col = row * 2 - 1;
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			if (Star[i][j] == 'x') break;
			printf("%c", Star[i][j]);
		}
		printf("\n");
	}
}

void solution() {
	int N;
	scanf("%d", &N);
	init_Star(N);
	set_Star(N, N, 0, 0);
	show_Star(N);
}

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

	solution();

	return 0;
}