[백준] 2447 별 찍기 - 10 (Python 파이썬)

https://www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

문제 설명

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***

* *

***

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

---

풀이 과정

이 문제는 분할 정복 문제로, 큰 문제를 작은 문제로 쪼개어 해결한다음 이를 이용해 큰 문제를 해결하는 문제이다.

먼저, 문제를 풀기 위해선 규칙부터 찾아야 한다.

 

가장 작은 3 x 3 부터 살펴보자.

*	*	*
*		*
*	*	*

5번 째 칸을 제외하고는 모두 별로 채워져 있다.

5번째 칸의 특징은 x, y 좌표 모두 1이라는 것이다. (1, 1)

 

그럼 이제 3 x 3을 3배 늘린 9 x 9를 살펴보자.

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

위 테이블을 보면 알 수 있듯이, 9 x 9 는 3 x 3의 테이블의 패턴이 똑같이 반복되어 나타남을 알 수 있다.

 

여기서, 9 x 9안에서의 3 x 3 하나를 한 칸이라고 생각해보자.

(즉, 3 x 3 패턴 하나를 한 칸으로 생각해보자.)

그럼, 9 x 9 테이블을 3 x 3 으로 생각해볼 수 있다.

 

이 때, 마찬가지로 가운데 부분만 비어있음을 알 수 있다.

 

3 x 3 에서 가운데 부분인 (1, 1) 만 비어있듯이,

9 x 9 에서 가운데 부분인 (3, 3) 부터 (5, 5) 까지의 부분만 비어있다.

 

마찬가지로 9 x 9 테이블을 3배 늘린 27 x 27 은

위의 9 x 9 의 패턴을 한 칸으로 취급하여 3배 늘린 모양이며, 가운데가 비어있다.

 

여기서 비어있는 곳의 특징이 있다.

처음엔 (1, 1), 그 다음엔 (3, 3)~(5, 5), 그 다음엔 (9, 9) ~ (17, 17) 이다.

이는 모두 각 행,열을 3^N으로 나누었을 때 몫이 1이라는 특징이 있다.

 

처음에는, 1로 나누었을 때의 몫이 1

그 다음에는, 3으로 나누었을 때 몫이 1

그 다음에는, 9으로 나누었을 때 몫이 1인 행,열 인 것이다.

 

이를 이용한 코드는 다음과 같다.

n = int(input())
star = ["***", "* *", "***"]
cnt = 0


def getStars(star):
    mat = []
    for i in range(3 * len(star)):
        if i // len(star) == 1:
            mat.append(star[i % len(star)] + " " * len(star) + star[i % len(star)])
        else:
            mat.append(star[i % len(star)] * 3)
    return mat


while n > 3:
    n /= 3
    cnt += 1

for i in range(cnt):
    star = getStars(star)

for i in star:
    print(i)

가장 기본적인 모양인

***

* *

*** 을 만들어 주고

n이 3 이상일 때 부터 반복패턴을 만들어 주기 위해 while문을 통해 몇 번 반복해야 할 지를 정한다.

그리고 나서 그 횟수만큼 반복하여 그려준다.

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !