백준 2447번

별 찍기 - 10

시간 제한 : 1 초 메모리 제한 : 256 MB

문제

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, …)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

---

• * *** N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

출력

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

해설

이 문제는 재귀적으로 별 패턴을 그리는 문제입니다. 주어진 규칙에 따라 별을 찍으면서 패턴을 생성합니다.

주요 개념은 다음과 같습니다:

1. 기본 패턴: 3 N=3일 때의 패턴은 ***
   • * *** 입니다.
2. 재귀적 패턴: N>3일 경우, N/3 크기의 패턴을 가지고 N 크기의 패턴을 생성합니다. 중앙 부분은 공백으로 채워지고, 나머지 부분은 작은 패턴이 8개 위치합니다.

다음과 같은 방법으로 문제를 해결합니다:

1. Base Case: N=3일 때의 기본 패턴을 반환합니다.
2. Recursive Case: N>3일 경우, N/3 크기의 패턴을 재귀적으로 호출하여 얻습니다.
3. N/3 크기의 패턴을 사용하여 N 크기의 패턴을 생성합니다. 중앙 부분은 공백으로 채우고, 나머지 부분에는 작은 패턴을 위치시킵니다.
4. 완성된 패턴을 반환합니다. 이 방법을 사용하면 주어진 규칙에 따라 별 패턴을 재귀적으로 생성할 수 있습니다.

def star(n):
    if n == 3:
        return ['***', '* *', '***']
    
    x = n // 3
    sub = star(x)
    result = []
    
    for i in range(n):
        if i // x == 1:
            result.append(sub[i % x] + ' ' * x + sub[i % x])
        else:
            result.append(sub[i % x] * 3)
            
    return result

n = int(input())
pattern = star(n)
for row in pattern:
    print(row)