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

작성일 :

문제 링크

2447번 - 별 찍기 - 10

설명

정사각형 영역을 재귀적으로 분할하며 특정 규칙에 따라 별과 공백을 배치하는 구현 문제입니다.

문제에서 주어진 내용을 자세히 살펴보면 다음과 같습니다:

  • 입력으로 하나의 정수 N이 주어지며, 이 값은 항상 \(3^k\) 형태입니다. (\(k\)는 1 이상의 정수)
    • 따라서 N은 3, 9, 27, 81, ... 등의 값만 가능합니다.
  • 출력해야 할 패턴은 N × N 크기의 정사각형 형태이며, 별(*)과 공백으로 구성됩니다.

  • 패턴 형성의 핵심 규칙은 다음과 같습니다:
    1. 전체 영역을 3×3 크기의 9개 블록으로 분할했을 때, 정중앙에 위치한 블록은 반드시 공백으로 채웁니다.
    2. 나머지 8개의 블록에 대해서는 동일한 규칙을 재귀적으로 적용합니다.
    3. 이러한 분할과 채우기 과정은 블록의 크기가 1×1이 될 때까지 계속됩니다.


예시

가장 작은 예시인 N = 3일 때의 패턴은 다음과 같습니다:

1
2
3

***
* *
***

여기서 가운데(1행 1열)가 공백인 이유는 3×3 영역에서 중앙 블록이기 때문입니다.

N = 9인 경우를 생각해보면, 전체 9×9 영역을 3×3 블록 9개로 나누고, 중앙 3×3 블록은 모두 공백으로 채웁니다.

그리고 나머지 8개의 3×3 블록 각각에 대해 N = 3일 때의 패턴을 적용합니다.

이렇게 만들어진 패턴은 다음과 같습니다:

1
2
3
4
5
6
7
8
9

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

N = 27인 경우는 더 복잡하지만, 9×9 패턴을 기본 단위로 하여 동일한 재귀적 규칙이 적용됩니다.

접근법

이 문제를 해결하기 위한 가장 효과적인 방법은 각 좌표가 별이어야 하는지 공백이어야 하는지를 판단하는 함수를 구현하는 것입니다.

전체 접근법은 다음과 같습니다:

  1. 입력으로 받은 N 크기의 정사각형 영역에서 각 좌표 (x, y)에 대해:
    • 해당 좌표가 별인지 공백인지 판단하는 함수를 호출합니다.
    • 판단 결과에 따라 별 또는 공백을 출력합니다.
  2. 특정 좌표가 별인지 공백인지 판단하는 과정:
    • 현재 다루는 영역의 크기를 size라고 할 때, 그 영역 내에서 좌표의 상대적 위치를 확인합니다.
    • 구체적으로는 x / size % 3과 y / size % 3가 모두 1이면, 해당 좌표는 3×3 분할에서 중앙 블록에 속하므로 공백입니다.
    • 그렇지 않으면, size를 3으로 나눈 값을 새로운 크기로 하여 재귀적으로 판단합니다.
    • 재귀 과정에서 size가 1보다 작아지면 더 이상 분할할 수 없으므로 별을 출력합니다.

핵심 로직

  • x / size % 3과 y / size % 3 :
    • x / size와 y / size는 현재 크기 기준으로 좌표가 어느 블록에 속하는지를 나타냅니다.
    • 이 값을 3으로 나눈 나머지는 3×3 분할에서 몇 번째 행/열에 속하는지를 알려줍니다.
    • 행과 열의 인덱스가 모두 1(즉, 중앙)이면 해당 좌표는 공백입니다.
  • 재귀적 판단:
    • 매 단계에서 영역의 크기를 3으로 나누어 더 작은 블록에서도 같은 규칙을 적용합니다.
    • 이 과정은 블록 크기가 1이 될 때까지 계속됩니다.

이러한 방식으로 모든 좌표에 대해 별 또는 공백 여부를 판단하여 전체 패턴을 완성합니다.

Code

[ C# ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

using System;
using System.Text;

class Program {
  static StringBuilder sb = new StringBuilder();

  static void Main() {
    int n = int.Parse(Console.ReadLine());

    for (int x = 0; x < n; x++) {
      for (int y = 0; y < n; y++)
        Recur(x, y, n);
      sb.AppendLine();
    }
    Console.Write(sb.ToString());
  }

  static void Recur(int x, int y, int size) {
    if ((x / size) % 3 == 1 && (y / size) % 3 == 1) {
      sb.Append(" ");
      return;
    } else {
      if (size / 3 == 0) sb.Append("*");
      else Recur(x, y, size / 3);
    }
  }
}

[ C++ ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <bits/stdc++.h>

using namespace std;

void recur(const int& x, const int& y, const int& n) {
  if ((x / n) % 3 == 1 && (y / n) % 3 == 1) {
    cout << " ";
    return;
  } else {
    if (n / 3 == 0) cout << "*";
    else recur(x, y, n / 3);
  }
}

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

  int n; cin >> n;
  for (int x = 0; x < n; x++) {
    for (int y = 0; y < n; y++)
      recur(x, y, n);
    cout << "\n";
  }
  return 0;
}

이 블로그의 다른 글