백준 2448(별 찍기) - Python(파이썬) - 재귀

2448번: 별 찍기 - 11

 

문제 설명

내가 처음 생각한 풀이는 이와 같다

위와 같이 삼각혁의 꼭짓점의 좌표를 (startX,startY,높이) 라고 가정해본다.

N=12 일 때의 삼각형은 연두색과 같이 세개로 나누어진다.

( 0, 0 6 ) , ( -6, 6, 6 ) ,( 6, 6, 6 )으로 이렇게 세개가 나누어진다. 

이걸 처음 시작점 ( 0, 0, 12) 점이랑 연관되어서 생각해보면 ( 0, 0, 6 ), ( 0-6, 0+6, 6 ), ( 0+6, 0+6, 6) 이라고 할 수 있다.

또 N = 6일 때의 값을 각각 세개의 삼각형으로 나눌 수 있다.

( 0 , 0 , 6 ) -> ( 0, 0, 3 ) , ( -3, 3, 3 ) , ( 3, 3, 3 )  -> ( 0, 0, 3) , ( 0-3, 0+3, 3) , ( 0-3, 0+3, 3)

( -6, 6, 6 ) -> ( -6, 6, 3) , ( -9, 9 , 3) , ( -3, 9, 3 ) -> ( -6, 6, 3 ) , ( -6-3, 6+3, 3) , (-6+3, 6+3, 3)

( -6, 6, 6 ) -> ( 6, 6 ,3) , ( 3, 9,3 ) , ( 9, 9, 3) -> ( 6, 6, 3 ), ( 6-3, 6+3, 3), ( 6+3, 6+3, 3)

즉, ( startX, startY, N )
=> ( startX, startY, (N//2) ), ( startX-(N//2) , startY+(N//2) , (N//2) ) , ( startX+(N//2) , startY+(N//2) , (N//2) )

 이런식으로 재귀한다는 것이다. 

그리고 계속 2로 나누다가 3이 되는 순간에는 

	i=-2	i=-1	i=0	i=1	i=2
j=0			O
j=1		O		O
j=2	O	O	O	O	O

j = 0 인 경우에는 i=0일 때만 성립한다.

j = 1 인 경우에는 i=-1 또는 i=1인 경우 성립한다.

j= 2 인 경우에는 모두 성립한다.

문제풀이
① 함수를 star(startX, startY, n , k ) 이렇게 선언했다.
startX 시작 x좌표, startY 시작 y좌표, n : 길이, k : 처음 n의 길이 저장용
k를 따로 저장한 이유는 n은 계속 변하기 때문에 따로 저장해야하는 k가 필요하여서 이런식으로 정리하였다. 
( k가 필요한 이유 ? 제일 큰 삼각형 위의 꼭짓점을 (0,0)이라고 가정하였는데 실제적으로 배열에서는 (k-1,0)이므로 나중에 계산 시 필요하여서 ) 
② nextn = n//2라고 가정 n==3인 경우를 제외하고
star(starX,startY,nextN,n,k), star(startX+nextn,start+nextn,n,k ), star(startX-nextn, startY+nextn, n, k) 을 한다.
③ n==3인 경우에는 for 루프로 i는 -2부터 2까지, j는 0부터 2까지 하지만 
 j==0인 경우 -> i==0 | j==1 -> i==1 , i==-1 | j==2인 경우에는 array[startY+j][startX+i+k-1 ] ="*"를 하게 한다.
( 이 때, 1번에서 말했듯이 옮겨야하므로 k-1를 더해주는 것이 중요하다 ) 

import sys
n = int(sys.stdin.readline())
#array 선언 ( 2n-1 * n 구조 )
array = [[" "]*(2*n-1) for _ in range(n)]

def star(startX,startY,n,k):
    #n==3인 경우
    if n == 3:
        for i in range(-2, 3, 1):
            for j in range(3):
                if (i == 0 and j == 0) or (j == 1 and i == -1) or (j == 1 and i == 1) or (j == 2):
                    array[startY + j][startX + i + k - 1] = "*"
        return
    #n==3이 아닌 경우
    else:
        #길이를 나누고
        nextn = n//2
        star(startX,startY,nextn,k)
        star(startX+nextn,startY+nextn,nextn,k)
        star(startX-nextn,startY+nextn,nextn,k)

#처음 스타트 점을 원점이라고 가정
star(0,0,n,n)
#프린트
for i in array:
    print("".join(i))