[Algorithm] 별찍기 - 18

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

10993번: 별 찍기 - 18

 

위 문제는 1~10 숫자를 받아 일정 패턴의 별을 찍어내는 문제이다.

 

해당 별의 n번째 모양은

마치 마법진처럼 전에 그렸던 (n-1 번째) 모양에 바깥쪽에

삼각형을 덧대어 그리는 형식이다.

 

해당 별 찍기는 2차원 배열을 이용하여 입력한 숫자에 따른 배열을 생성하고

일정 패턴에 맞는 자리에 * 모양을 대입하면 된다.

(말은 쉽지 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ)

 

 

 

이 문제는 거의 수학문제이다.

 

먼저 입력받은 n에 따른 배열의 크기를 정하는 식은 다음과 같다.

n = 1
row = 1, col = 1

n = 2
row = 1 + 4, col = 1 + 2

n = 3
row = 1 + 4 + 8, col = 1 + 2 + 4

...

n = k
row = 1 + 4 + ... + 2^k, col = 1 + 2 + ... + 2^k-1

즉 row와 col은 입력받은 n에 따른 각각의 등비수열의 합을 구해주면 된다.

row : An = 2^(n+1) 의 등비수열의합 - 2

col : An = 2^(n-1) 의 등비수열의 합



row = 2^(n+1) -3

col = 2^n -1

 

row 와 col을 구해줬다면

이제는 별을 어떻게 찍을것인지 생각해 봐야 한다.

출력 예제를 보게 되면

n이 짝수일때와 홀수일때 삼각형의 모양이 위아래로 뒤집히게 되는 것을 볼수있다.

 

이를 코드로 추상화 해보면

입력받은 n 이 1이될때 까지 감소시켜 1이 될때까지의

n일 때의 바깥쪽 삼각형 좌표를

2차원 배열안에 넣어주면 된다.

 

즉, 재귀를 이용하여 n을 1씩 감소시키고

그 해당하는 시작 x,y 좌표 를 구하여

다음 재귀의 매개변수로 넘겨주면 되는 것이다.

 

이를 의사코드로 작성하면 다음과 같다.

def 별찍기함수(깊이(n),x,y):
	
    깊이가 1일때
    	배열(x,y) = '*'
    
    
    깊이가 짝수일때:
    	역삼각형 그리기
        별찍기함수(n-1,다음x좌표,다음y좌표)
    깊이가 홀수일때:
    	정삼각형 그리기
        별찍기함수(n-1,다음x좌표,다음y좌표)

자 그러면 여기서 위의 의사코드를 구현해보면 다음과 같이 구현할 수 있다.

 

먼저 정삼각형 모양을 출력하기 위한 표현을 다음과 같이 작성할 수 있다.

        
        for i in range(x,row+x): 
            # 맨 아랫줄은 모두 *로 표시.
            Map[y+col-1][i] = '*'
            
        for i in range(col):
            # 위쪽 (y=0) 에서 부터 x의 중앙점 에서 앞뒤로 +-i번째 배열에 *표시.
            Map[y+i][x+row//2-i]='*' 
            Map[y+i][x+row//2+i]='*'
            

 

역삼각형 그리기는 위와 반대로 생각하여 그리면 된다.

        for i in range(x,row+x):
            # 첫 줄은 모두 * 로 표시
            Map[y][i] = '*'
            
        for i in range(col):
            # 나머지 줄은 양 끝쪽 위치에서 +-i번째 위치에 * 표시.
            Map[y+i][x+i] = '*'
            Map[y+i][x+row-1-i] = '*'
            

 

마지막으로 재귀함수를 이용하기위해

다음 그려질 시작점 위치를 계산해야 한다.

 

 

이제 위에 정리한 식들을 직접 코드로 구현하면 다음과 같이 구현할 수 있다.

 

def draw_stars(depth, x, y):
    # 재귀 탈출조건
    if depth ==1 :
        Map[y][x] = '*'
        return
    row = pow(2,depth+1) - 3
    col = pow(2,depth)- 1
    # 짝수일때
    if depth % 2 == 0:
        for i in range(x,row+x):
            Map[y][i] = '*'
        for i in range(col):
            Map[y+i][x+i] = '*'
            Map[y+i][x+row-1-i] = '*'
        # 재귀 호출
        draw_stars(depth-1,pow(2,depth-1)+x,y+1)
    # 홀수 일때
    else:
        for i in range(x,row+x):
            Map[y+col-1][i] = '*'
        for i in range(col):
            Map[y+i][x+row//2-i]='*'
            Map[y+i][x+row//2+i]='*'
        # 재귀 호출
        draw_stars(depth-1,pow(2,depth-1)+x,y+col//2)

 

마지막 으로 입력과 출력은 기본적인 Python 문법으로 작성해 주면 해당 문제를 해결할 수 있다!

 

n= (int)(input())
row = pow(2,n+1)-3
col = pow(2,n)-1
Map = [[' ']*row for _ in range(col)]
draw_stars(n,0,0)

if n % 2 == 0:
    for i in range(col):
        for j in range(row-i):
            print(Map[i][j], end="")
        print()
else:
    for i in range(col):
        for j in range(row-col+i+1):
            print(Map[i][j], end="")
        print()

 

 

완성!