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

풀이 시간: 57m13s61(고민) + 28m16s94(참고)

시간 복잡도: O(NlogN)

공간 복잡도: O(N^2)

참고 자료: https://youtu.be/WjmEVp-Lgns?si=XVtJgDCWHFl45pv6

문제

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

입력

첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수)

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

문제 풀이

문제를 분석해봤지만, 발상이 잘 떠오르지 않아서 일단 냅다 삼각형부터 만들어보았다.

#include <iostream>
using namespace std;
int N;

void triangle() {
    int odd = 1, width = N * 2 - 1;
    for (int i = 0; i < N; ++i) {
        int blank = (width - odd) / 2;
        for (int j = 0; j < blank; ++j) cout << " ";
        for (int j = 0; j < odd; ++j) cout << "*";
        for (int j = 0; j < blank; ++j) cout << " ";
        cout << "\n";
        odd += 2;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N;
    triangle();
    return 0;
}

N번의 줄을 돌면서, 삼각형 맨 밑줄 길이를 width로 잡고, 공백과 별을 나누어 출력했다.

그러나 이렇게만해서는 원하는 삼각형을 구할 수가 없다.

작은 삼각형부터 재귀 형식으로 하나씩 호출하여 삼각형을 채워나가야 한다.

 

그냥 한 줄씩 바로 출력해야한다고 생각했는데, 다른 참고 자료를 보니 배열을 생성해서 값을 다 저장한 후 출력하는 것이었다.

*. 다음 유튜브 영상을 참고하였다.

https://youtu.be/WjmEVp-Lgns?si=XVtJgDCWHFl45pv6

 

다시 생각해보면 k가 10까지로 제한되어있기 때문에 배열이 더 커지지는 않는다.

 

💁🏻‍♀️ 초기 x가 N - 1인 이유? 

만약 N이 3일 경우, N - 1 = 2로, 맨 상단 2번째 위치에서부터 별이 출력된다. (인덱스는 좌측 기준 0번부터 시작)

즉, 가로로 2번째 위치에서 별이 출력되는 곳이 삼각형의 꼭대기 좌표이다.

N이 3이 아닌 나머지 경우는, 작은 삼각형으로 쪼개지기 때문에 현재 x좌표를 기준으로 계산하여 작은 삼각형 3개의 x좌표를 다시 갱신해야 한다.

• x - (n / 2): 좌측 하단 삼각형의 맨 꼭대기 x좌표
• x + (n / 2): 우측 하단 삼각형의 맨 꼭대기 x좌표
• y + (n / 2): 하단의 두 삼각형의 맨 꼭대기 y좌표

전체 코드

#include <iostream>
using namespace std;
int N;
char arr[3072][6144]; // 행(N), 열(2*N-1)

void star(int n, int x, int y) {
    if (n == 3) { // 가장 작은 삼각형 별 찍기
        arr[y][x] = '*';
        arr[y + 1][x - 1] = '*';
        arr[y + 1][x + 1] = '*';
        arr[y + 2][x - 2] = '*';
        arr[y + 2][x - 1] = '*';
        arr[y + 2][x] = '*';
        arr[y + 2][x + 1] = '*';
        arr[y + 2][x + 2] = '*';
        return;
    }
    // n이 3이 아닌 경우, 작은 삼각형 3개로 쪼개어 재귀 호출
    star(n / 2, x, y);
    star(n / 2, x - (n / 2), y + (n / 2));
    star(n / 2, x + (n / 2), y + (n / 2));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N;
    for (int i = 0; i < N; ++i) // 배열 초기화
        for (int j = 0; j < 2 * N; ++j)
            arr[i][j] = ' '; // 공백

    star(N, N - 1, 0); // 삼각형 꼭대기 (x, y)좌표

    for (int i = 0; i < N; ++i) { // 배열 출력
        for (int j = 0; j < 2 * N; ++j)
            cout << arr[i][j];
        cout << '\n';
    }

    return 0;
}

 

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

2448번: 별 찍기 - 11