문제
재귀적인 패턴으로 별을 찍어 보자. 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번째 줄까지 별을 출력한다.
코드
n = int(input())
def star(n):
if n == 3:
return ["***", "* *", "***"]
stars = star(n//3)
arr = []
for s in stars:
arr.append(s*3)
for s in stars:
arr.append(s + ' '*(n//3) + s)
for s in stars:
arr.append(s*3)
return arr
print('\n'.join(star(n)))
N이 3의 배수로만 주어지기 때문에 Divide & Conquer로 해결할 수 있는 문제였다.
N이 3, 9, 27일 때의 출력을 각각 그려보면 다음과 같다.
N이 3일 때가 가장 최소 단위이므로 star 함수의 입력값으로 3이 들어온다면 ["***", "* *", "***"] 배열을 리턴해주어서 위 그림에서 N=3일때의 그림이 배열에 저장되도록 한다. N이 3보다 큰 제곱수들일 때는 star(n//3)의 리턴 값을 이용하여 정해진 패턴에 따라 그려주면 된다. 이 문제에서는 star(n//3)의 패턴을 가운데만 뻥 뚫린 모양으로 그려주면 되므로 다음과 같이 코드를 작성한 것이다.
stars = star(n//3)
arr = []
for s in stars:
arr.append(s*3)
for s in stars:
arr.append(s + ' '*(n//3) + s)
for s in stars:
arr.append(s*3)
'문제풀이 > 분할정복' 카테고리의 다른 글
[Python/파이썬] 백준 4256번 트리 (0) | 2023.05.09 |
---|---|
[Python/파이썬] 백준 2448번 별 찍기 - 11 (0) | 2023.05.08 |
[Python/파이썬] 백준 1074번 Z (0) | 2023.03.15 |
[Python/파이썬] 백준 1992번 쿼드트리 (0) | 2023.03.15 |
[Python/파이썬] 백준 18222번 투에-모스 문자열 (0) | 2023.03.15 |