[백준] 2447번: 별 찍기 - 10

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

2447번: 별 찍기 - 10

 

아이디어를 생각하기까지 많은 시간이 걸렸다. 알고리즘 분류를 보니 '재귀'를 이용하여 푸는 문제였다.

최대한 재귀적으로 구현하려고 소스코드를 짜보았다.

import sys
input = sys.stdin.readline

cell = ['***', '* *', '***']

def drawStar(num):
    a = num//3
    temp = []
    if a == 1:
        return cell
    else:
        for x in drawStar(a):
            x = x*3
            temp.append(x)
        temp = temp*3
        for i in range(a, 2*a):
                temp[i] = temp[i][:a] + (' ' * a) + temp[i][num-a:]
        return temp

n = int(input())

for line in drawStar(n):
    print(line)

크기 3의 패턴을 기본셀(단위)로 보았다. 한 라인 별로, cell이라는 문자열에 리스트로 저장했다.

 

규칙성을 찾아보기 위해 함수 drawStar(3)의 반환값과 함수 drawStar(9)의 반환값을 비교해보겠다.

 

---

drawStar(3) == ['***', '* *', '***']

drawStar(9) == ['*********', '* ** ** *', '*********', 
		'*********', '* ** ** *', '*********',
                '*********', '* ** ** *', '*********']
                
# 찾은 규칙 : drawStar(3)의 각 요소를 3배 반복해서 늘리고, 전체 리스트를 3배 반복해서 늘린다.

하지만 여기서 빼먹은 것이 하나 있다.

바로 가운데에 공백이 있다는 조건을 빼먹은 것이다.

 

노트에 그림을 그려보면 알겠지만, 

n이 9일 때, drawStar(9)[3][3:6], drawStar(9)[4][3:6], drawStar(9)[5][3:6] 이 공백임을 알 수 있다. (index 3부터 3개 공백) 

n이 27일 때에는 어떨까?

예제 출력 1을 보면, index가 9부터 9개가 연속으로 공백인 것 만 빼고는 동일하다. 

 

위 소스코드의 16~17번째 라인에 이와 같은 규칙성을 적용한 것을 구현하였다.

 

제출 결과