[백준 2448] 별 찍기 - 11 (C#, C++) - soo:bak

문제 링크

2448번 - 별 찍기 - 11

설명

높이 N, 가로 길이 2N - 1의 삼각형 모양 별 패턴을 출력하는 문제입니다. 입력 N은 3 × 2^k 형태입니다.

가장 작은 기본 패턴은 N = 3일 때 높이 3, 폭 5의 삼각형입니다.

이 기본 패턴을 재귀적으로 조합하여 더 큰 삼각형을 만듭니다.

접근법

재귀적으로 Sierpinski 삼각형을 구성합니다. 가장 작은 단위는 높이 3인 삼각형입니다.

  *
 * *
*****

높이가 3보다 큰 경우, 전체 삼각형을 절반 높이의 작은 삼각형 세 개로 나누어 그립니다.

상단 중앙에 하나, 좌하단에 하나, 우하단에 하나를 배치하는 방식입니다.

각 작은 삼각형도 같은 방식으로 재귀적으로 나누어집니다.

예를 들어 높이 12인 삼각형은 높이 6인 삼각형 세 개로 나뉩니다.

높이 6인 삼각형은 다시 높이 3인 삼각형 세 개로 나뉘며, 높이 3인 삼각형은 더 이상 나누지 않고 그립니다.

전체 보드 크기는 높이 N, 가로 2N - 1입니다. 처음에는 모든 칸을 공백으로 채운 후, 별이 필요한 위치만 채워나갑니다.

---

Code

C#

using System;
using System.Text;

namespace Solution {
  class Program {
    static char[][] board = default!;

    static void Draw(int size, int row, int col) {
      if (size == 3) {
        board[row][col + 2] = '*';
        board[row + 1][col + 1] = '*';
        board[row + 1][col + 3] = '*';
        for (var i = 0; i < 5; i++) board[row + 2][col + i] = '*';
        return;
      }

      var half = size / 2;
      Draw(half, row, col + half);
      Draw(half, row + half, col);
      Draw(half, row + half, col + 2 * half);
    }

    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var width = 2 * n - 1;

      board = new char[n][];
      for (var i = 0; i < n; i++) {
        board[i] = new string(' ', width).ToCharArray();
      }

      Draw(n, 0, 0);

      var sb = new StringBuilder();
      for (var i = 0; i < n; i++) {
        sb.Append(board[i]);
        sb.Append('\n');
      }

      Console.Write(sb.ToString());
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<string> vs;

vs board;

void draw(int size, int row, int col) {
  if (size == 3) {
    board[row][col + 2] = '*';
    board[row + 1][col + 1] = '*';
    board[row + 1][col + 3] = '*';
    for (int i = 0; i < 5; i++) board[row + 2][col + i] = '*';
    return;
  }

  int half = size / 2;
  draw(half, row, col + half);
  draw(half, row + half, col);
  draw(half, row + half, col + 2 * half);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  int width = 2 * n - 1;
  board.assign(n, string(width, ' '));

  draw(n, 0, 0);

  for (int i = 0; i < n; i++)
    cout << board[i] << "\n";

  return 0;
}