[BOJ] 백준 10993 별 찍기 - 18

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

 Input 
3

 Output 

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

 

 

n이 증가함에 따라 별들의 모양을 분석하면 안쪽의 별들을 에워싸는 형태입니다.

그렇기에 별들의 메모리 공간을 잡아서 모양을 만든 후 출력.

 

삼각형의 높이 변화: 1 → 3 → 7 → 15  →  2n- 1

삼각형의 너비  변화: 1 → 5 → 13 → 29  → 2 * 높이 - 1

(1 ≤ n ≤ 10 이므로, 삼각형의 최대 높이 = 1023,  최대 너비 = 2045)

 

▶ 바깥쪽부터 시작해서 안쪽 삼각형을 채워갑니다.

▶ 각 삼각형의 시작점을 어떻게 알 수 있을까요?

    ① 초기값은 입력받은 n값과 삼각형의 높이를 이용해 쉽게 구할 수 있습니다.

        [n = 짝수] → (2n- 1 - 1, 2n- 1 - 1) = (2n- 2, 2n- 2)

                         ex) n = 4 일 때, (14, 14)

        [n = 홀수] → (0, 2n- 1 - 1) = (0, 2n- 2)

                         ex) n = 3 일 때, (0, 7)     

    ② 다음(안쪽) 삼각형의 시작점 = 이전 삼각형 시작점 ± (높이-1) ± 1

        부호는 left, right가 형성하는 방향에 따라 다릅니다. (x 좌표만 변하면 y 좌표는 동일)

        ex) [UP] 14 - (15 - 1) + 1 → (1, 14)

        ex) [DOWN] 1 + (7 - 1) - 1 → (6, 14)

        ex) [UP] 6 - (3 - 1) + 1 → (5, 14)

        ※ n이 짝수이면 UP 방향으로 시작 / 홀수이면 DOWN 방향으로 시작

        ※ 코드상에서는 굳이 계산하지 않고 변수에 따로 저장하여 처리

 

▶ 시작점을 중심으로 left, right을 뻗어나가듯이 형성합니다.

    마지막 단계에는 left와 right 사이를 *로 채웁니다.

 

▶ [문제] BOJ 별 찍기 시리즈

[문제] BOJ 별 찍기 시리즈

---

* 출력할 때, 바깥쪽 삼각형의 오른쪽 공백은 출력하지 않도록 설정.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
 
char map[1023][2045];
void drawStar(int n, int x, int y, bool dir) {
    // 시작점
    map[x][y] = '*';
    // 마지막 단계라면 return
    if (n == 1) return;
 
    // 삼각형의 높이
    int height = (1 << n) - 1;
    int left = y, right = y;
    for (int i = 1; i < height; i++) {
        if (dir) x--; // UP
        else x++; // DOWN
 
        left--; right++;
        map[x][left] = '*'; map[x][right] = '*';
    }
 
    //  마지막 단계에서는 left와 right 사이에 '*'로 채움
    for (int j = left + 1; j < right; j++) {
        map[x][j] = '*';
    }
 
    // 안쪽 삼각형의 시작점 x 좌표 계산
    if (dir) x++;
    else x--;
 
    drawStar(n - 1, x, y, !dir);
}
 
int main(void) {
    int n;
    cin >> n;
 
    // 모든 영역을 공백으로 초기화
    int height = (1 << n) - 1;
    int width = 2 * height - 1;
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            map[i][j] = ' ';
        }
    }
 
    bool dir = false; // DOWN
    if (n % 2 == 0) dir = true; // UP
 
    int x = 0;
    if (dir) x = (1 << n) - 2;
    int y = (1 << n) - 2;
 
    drawStar(n, x, y, dir);
 
    // 출력할 때, 바깥쪽 삼각형의 오른쪽 공백은 출력하지 않도록 설정.
    if (dir) {
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                printf("%c", map[i][j]);
            }
            width--;
            cout << "\n";
        }
    }
    else {
        for (int i = 0; i < height; i++) {
            for (int j = 0; j <= y; j++) {
                printf("%c", map[i][j]);
            }
            y++;
            cout << "\n";
        }
    }
 
    return 0;
}