[백준] 2447. 별 찍기 - 10

별 찍기 - 10

분류

• 재귀
• 분할 정복

문제 설명

재귀적인 패턴으로 별을 찍어 보자. 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번째 줄까지 별을 출력한다.

예제 입력 & 출력

입력: 3
출력: 
***
* *
***


입력: 27

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

### 문제풀이 문제 30분을 고민해도 잘 풀리지가 않아 이해가 쉬운 풀이를 참고하여 다시 연습해봤다. 풀이가 쉬우면서도 다시 보니 분할 정복 부분이 엄청 매력적인 문제였다고 생각한다. 재귀는 풀이를 보면 바로 이해가 되는 데 풀 때는 왜 그런 생각을 하기 힘든 지..ㅠ 재귀 문제들을 열씨미 공부하자,,,

python 문제 풀이

def stampStars(N):
	# 탈출 조건! 1이면 ['*'] 리턴
    if N <= 1:
        return ['*']
    
    result = []
    # 이 문제는 3의 거듭제곱이기 때문에 3의 몫을 재귀시킨다.
    Stars = stampStars(N//3)
    
    # for문을 3개 만들어준다. 3은 ['*']로, 9를 넣으면 ['***', '* *', '***']를 통해 계산한다.
    for S in Stars:
        result.append(S*3)
    for S in Stars:
        result.append(S + ' ' * (N//3) + S)
    for S in Stars:
        result.append(S*3)
    
    return result

print("\n".join(stampStars(int(input()))))

참고

• [백준 2447번] 별 찍기 - 10 in python
• 백준 파이썬 2447 별찍기 - 10