[백준, python 파이썬] 2447번 : 별찍기-10(재귀)
백준 2447번 문제 풀기
https://www.acmicpc.net/problem/2447
2447번: 별 찍기 - 10
재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이
www.acmicpc.net
문제 설명
문제
재귀적인 패턴으로 별을 찍어 보자. 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번째 줄까지 별을 출력한다.
|
예제 입력 1
|
예제 출력 1
|
|
27
|
|
알고리즘 및 설명
내가 알고리즘 문제를 풀면서 (아직 쉬운 문제만 풀어서 그런거겠지만) 푸는데 가장 오래 걸린 문제이다. 처음엔 이중 for문을 사용하여 구현했는데 그러다보니 차원이 커질수록 너무 시간이 오래걸려서 시간초과가 떴었다. 모든 알고리즘 구현이 그렇듯이 규칙을 생각해야하는데, 이 규칙은 감이 잡히면서도 감이 잡히지 않았다. 이 문제에도 여러 규칙들이 있겠지만 그 중 내가 찾은 규칙은 아래와 같다.
3의 제곱들이다보니 모두 세 부분으로 나누면 A-B-A로 나눠지고, 또 그 A도 A-B-A로 쪼개진다는 것이다.
아래의 그림으로 예를 들어보자면,
입력값이 9인 경우, 4번 째 행은 A = [* * * *] + B = [* * * *] + A = [* * * *] 로 나눌 수 있으며 A도
A' = [* *] + B' = [ ] + A' = [* *]로 나누어진다.
공백이 생기는 규칙은 입력 값을 N이라고 하면 N을 가로 세로로 삼등분하여 정사각형의 중앙에 공백을 채우는 것이다.
이 규칙을 토대로 재귀 함수를 사용해 구현한 코드는 아래와 같다.
import math ##math.log를 사용하기 위해 라이브러리 호출
n = int(input()) ##입력값 받기
space = [] ##space: 3,9,27... 의 중간 공백 자리를 받기 위한 list
for i in range(round(math.log(n,3))):
num = 3**(i+1)
space.append(list(range(num)[int(num/3):int(num/3)*2]))
def SET_STAR(i, N, space): ##재귀함수 생성
if N == 3: ##3인 경우 초기값 생성(이를 기준으로 확장)
A = "*"
if i % N == 1: ##행의 index가 3으로 나눴을 때 나머지가 1인 경우만 공백
B = " "
else: ##나머지는 *
B = A
else:
j = round(math.log(N,3))
A = SET_STAR(i, N//3, space) ##A에 들어가는 문자열은 N//3을 기준으로 재귀
if i % (3**(j)) in space[j-1]: ##3 이외의 입력값의 공백 자리인 index는 공백으로 채우기
B = " "*(N//3)
else: ## 그렇지 않으면 A와 동일하게
B = A
return A+B+A
for i in range(n):
ANS = SET_STAR(i, n, space)
print(ANS)