[BOJ] 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과 같다.

 

문제 해결

import sys
input = sys.stdin.readline

def star(n):
    if n == 1:
        return ['*']
    stars = star(n // 3)
    print(f'stars = {stars}')
    tmp = []
    for i in stars:
        tmp.append(i * 3)
    for i in stars:
        tmp.append(i + ' ' * (n//3) + i)
    for i in stars:
        tmp.append(i * 3)
    print(f'tmp= {tmp}')
    return tmp


N = int(input())
print('\n'.join(star(N)))

 

문제 풀이 설명

재귀 파트의 마지막 문제다.

항상 3의 거듭제곱의 수가 N으로 입력되고, 출력 시 가운데 공간만 별이 비어있는 상태로 출력하면 된다.

재귀 문제의 해결방법은 항상 처음 문제해결방법에 있는 것 같다.

먼저 가장 작은 단위인 N = 3 일때를 가정해 문제 풀이를 시작했다.

또한 파트를 3개로 나눠 1. 출력의 첫 번째 줄 2. 출력의 두 번째 줄 3. 출력의 세 번째 줄로 나눴다.

star 함수의 첫 번째 for문에서 1번, 두 번째 for문에서 2번, 세 번째 for문에서 3번을 tmp 리스트에 append 해줬다.

 

N이 3일때는 stars 가 '*' 가 되며, 각 세개의 for문을 돌고나면 출력문처럼 완성된다. 그 후 함수가 끝나고 출력해주면 정답이 나온다.

#N = 3 일때
stars = ['*']
tmp= ['***', '* *', '***']

N이 9일때는 star 함수가 N이 3일때로 호출이 한번 되고, tmp가 완성된 후 return하면 stars가 출력문처럼 나온다.

# N = 9 일때
stars = ['***', '* *', '***']
tmp= ['*********', '* ** ** *', '*********', '***   ***', '* *   * *', '***   ***', '*********', '* ** ** *', '*********']

그 후 stars로 세개의 for문을 돌리면 정답이 나온다.

생각하기 어렵지만 재귀 문제를 계속 풀다보면 감이 잡히는 것 같아 다행인 것 같다.

 

문제 풀이 알고리즘

1. 최소 단위일 때 알고리즘을 설계한다.

2. 그 이후 재귀 함수를 호출 할 방법을 설계한다.

3. 해당 문제에서는 n이 3일때 최소 단위

4. stars 변수를 통해 재귀 함수를 호출

5. 완성된 리스트를 return해 점점 크기를 키워 나간다. => stars를 가지고 for문을 돌기 때문에 점점 커진다.