백준 2448번 [별 찍기-11](C++)-yes6686- 티스토리

백준 문제 풀이: 2448 [별 찍기 - 11]

---

문제 링크: https://www.acmicpc.net/problem/2448

문제 설명:

삼각형 모양의 별을 출력하는 문제입니다. 주어진 높이 n은 3×2^k 형태(3, 6, 12, ...)로 주어집니다. 높이 n에 맞는 별의 배열을 출력합니다.

입력:

• 첫째 줄에 높이 n이 주어집니다. (3 ≤ n ≤ 3×2¹⁰)

출력:

• 높이 n의 삼각형 모양으로 출력된 별 배열을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <vector>
using namespace std;

vector<string> star;

// 삼각형 별 패턴을 재귀적으로 생성하는 함수
void draw(int n, int x, int y) {
    if (n == 3) {
        star[x][y] = '*';
        star[x + 1][y - 1] = '*';
        star[x + 1][y + 1] = '*';
        for (int i = -2; i <= 2; i++) {
            star[x + 2][y + i] = '*';
        }
        return;
    }

    int m = n / 2;
    draw(m, x, y);          // 위쪽 삼각형
    draw(m, x + m, y - m);  // 왼쪽 아래 삼각형
    draw(m, x + m, y + m);  // 오른쪽 아래 삼각형
}

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

    int n;
    cin >> n;

    // 초기화
    star.assign(n, string(2 * n - 1, ' '));

    // 패턴 생성
    draw(n, 0, n - 1);

    // 출력
    for (const auto &line : star) {
        cout << line << '\n';
    }

    return 0;
}

예제

입력:
3

출력:
  *
 * *
*****

입력:
6

출력:
     *     
    * *    
   *****   
  *     *  
 * *   * * 
***** *****

---

코드 설명

• 재귀적 접근: 문제의 삼각형 패턴은 작은 삼각형을 재귀적으로 조합하여 생성됩니다.
• 기저 조건: 높이가 3일 때, 기본 삼각형 패턴을 생성합니다.
• 분할 및 재결합: 현재 삼각형을 세 개의 작은 삼각형으로 분할하고, 각각 재귀적으로 채웁니다.
• 출력: 최종적으로 완성된 배열을 출력합니다.

시간 복잡도

• 재귀적으로 삼각형을 생성하므로 시간 복잡도는 O(n log n)입니다.
• 높이가 최대 3×2¹⁰인 경우도 효율적으로 작동합니다.

---

결과

코드는 입력된 높이 n에 맞는 삼각형 별 패턴을 정확히 출력합니다. 재귀적인 접근 방식을 사용하여 문제를 효율적으로 해결합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!