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

문제 링크

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

문제

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

 

입력 예시

27

출력 예시

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

 

풀이 전 생각

 백준 사이트의 문제 분류 중 재귀 파트에 해당하는 문제인데, 언뜻 보기에 반복되는 패턴이 보여서 반복문으로도 풀 수 있지 않을까? 하는 생각이 들었다. 별 모양이 만들어지는 알고리즘을 순서대로 구체화해보면 다음과 같을 것 같다.

 

1.우선,

N은 3의 거듭제곱(3,9,27,...)꼴 이므로 가장 기본적인 단위는 N이 3일때 즉,

***
* *
***

 이러한 형태이다.

 

2.다음 단계인 N이 9일 때를 보자.  

1~3행에서는 기본단위가 3번 반복,

4~6행에서는 기본단위가 1번 + 빈 공간 + 기본단위가 1번

7~9행에서는 기본단위가 3번 반복된다.

 

3.다음 단계인 N이 27일 때를 보자.

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

1~9행에서는 2의 결과가 3번 반복,

10~18행에서는 2의 결과가 1번 + 빈 공간 + 2의 결과가 1번

19~27행에서는 2의 결과가 3번 반복된다.

 

4.결국, 별찍기 알고리즘 -> 나온 결과1 -> 별찍기 알고리즘 -> 나온 결과2 -> ...  이런 식으로 특정 알고리즘에서 나온 결과를 다시 특정 알고리즘에 집어넣으면 된다.

 

 

예제 코드(반복문)

def get_stars(stars):
    s=[]
    for i in range(len(stars)*3):
        if i//len(stars) == 1:
            s.append(stars[i%len(stars)]+' '*len(stars)+stars[i%len(stars)])
        else:
            s.append(stars[i%len(stars)]*3)    
    return s

N=int(input())

repeat = 0
while True:
    if N==3:
        break
    N = N//3
    repeat+=1

stars=['***','* *','***']

for i in range(repeat):
    stars = get_stars(stars)
        
print('\n'.join(map(str,stars)))

 

생각

 한 5시간 넘게 걸린 것 같다. 지금에서야 문제를 다시 보면 반복되는 패턴이 쉽게 보이는데, 처음 보았을 때는 '반복되는 규칙을 찾는 것'과 '이를 코드로 구현하기 위한 일련의 과정'을 정리하는 데 시간이 정말 많이 걸렸다. 또, 정리한 내용을 코드로 작성하는 것도 아직 많이 미숙한 것 같다. 어느정도 여러 카테고리의 문제를 풀어보고 경험을 조금 쌓은 후에는 시간 단축을 위해서 문제에 접근하고 해결하는 방식을 체계화하는 과정이 꼭 필요할 것 같다.

 

 

*재귀로도 풀어보고 내용 추가하기.