요즘 알고리즘과 프로그래밍언어 같이 공부하기 글과 같이 백준온라인의 '단계별로 풀어보기'를 통해 문제를 풀고 있습니다.

그 중 '별찍기 11 - 2448'에 대한 풀이 입니다.


주어진 라인수만큼 별을 찍는 문제인데요 라인수 N은 3, 6, 12, 24, 48, ... 와 같이 3*2^k (k <=10) 입니다.

N = 3 일 때, 아래와 같이 프린트해야하며 아래 삼각형이 기본 단위가 되겠습니다.

***
***
*****


N = 6 일 때,

******                        
***** *                       
********                      
*********                     
**********                    
***********


N = 12 일 때,

************                        
*********** *                       
**************                      
***************                     
****************                    
*****************
******************
***** *********** *
********************
*********************
**********************
***********************


요런 식인데요, 잘 보면 규칙성이 있습니다.

다음 단계 삼각형은 현 단계 삼각형 두 개가 아래에 위치하 것과 같은 모양이 됩니다.

그래서 저는 다음과 같이 문제를 풀었습니다.

"현 단계 삼각형 두 개를 만들어서 뒤에 붙이고 현 단계 삼각형을 오른쪽으로 민다."


N = 6 일 때,

1. 현 단계 삼각형

***
***
*****

2. 현 단계 삼각형 두 개를 만들어서 뒤에 붙인다

***                        
** *                       
*****                      
*********                     
**********                    
***********

3. 현 단계 삼각형을 오른쪽으로 민다.

******                        
***** *                       
********                      
*********                     
**********                    
***********


위의 3번에서 "현 단계 삼각형을 오른쪽으로 민다"고 했는데요,

그렇다면 '오른쪽으로 얼마나 밀어야하는가?'가 문제입니다.

요것도 규칙이 있습니다.

기본적으로 아래와 같이 삼각형을 갖고 있다면,

***
***
*****

N = 3 일 때, 0칸

N = 6 일 때, 3칸

N = 12 일 때, 6칸

...

N = 3 × 2^k 이므로, 오른쪽으로 미는 칸 수는 바로 3 × 2^(k - 1)가 되겠습니다. 아래와 같은 수식으로 k를 구할 수 있습니다.

log₂(N ÷ 3) = log₂(3 × 2^k ÷ 3) = log₂2^k = k


구현은 파이썬 언어를 사용했습니다.

저는 기본 삼각형을 아래와 같이 1차원 배열로 선언하고

s = ["  *   ", " * *  ", "***** "] #삼각형 사이에 빈 칸 하나 있음을 고려


다음 단계 삼각형을 만드는 함수를 아래와 같이 선언했습니다.

def makeStar(shift):
    c = len(s)
    for i in range(c):
        s.append(s[i] + s[i]) #현 단계 삼각형을 뒤에 붙이고
        s[i] = ("   " * shift + s[i] + "   " * shift) #현 단계 삼각형을 오른쪽으로 민다

전체 소스코드 입니다.


+ Recent posts