[백준] 별 찍기 - 11

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

2448번: 별 찍기 - 11

재귀를 이용하는 문제입니다.

 

우선 문제부터 요약하면, 첫쨰줄부터 N번째 줄까지 별을 출력해야 하는 문제입니다. 

N은 항상 3×2^k의 형태로 주어지며, 간단한 예시로는 

k=0 -> N=3

k=1 -> N=6

k=2 -> N=12

다음과 같이 규칙성이 있게 출력이 되어야 합니다. 

 

<Solution>

문제에 대한 이해 자체는 쉽습니다. 구현은 어떻게 해야할까요? 

 

위의 표 안의 상황에서 k=0에서 k=1로 변하는 상황을 통해 이후에도 같은 과정을 반복해서 더 큰 별들을 만들수 있도록 생각을 진행시켜 봅시다. 

 

아이디어 1. 

새로 만들어지는 별의 첫째 부분 별은 이전의 별을 들여쓰기 한 것이다.

 

이 말이 무슨 이야기 인가 하면, 

위의 그림처럼 새로 만들어 지는 별에서 가장 위의 부분별은 기존 별의 가장 아래의 길이(위에서는 5)를 2로 나눈 것을 올림한 결과 만큼 들여쓰는 것입니다. (위의 그림에서는 5//2 + 1)

 

아이디어 2. 

이후의 두 별은 기존 별과 별을 이어주면서 space한칸이 있다 라는 것입니다. 아래 그림을 보면 이해가 좀더 쉬울 것입니다.

이제 이 두 아이디어로 기존의 별을 통해 새로운 별을 만드는 방법을 알아 냈습니다.

이제 함수를 구성하여 k번(N = 3*2^k) 만큼 새로운 별을 만드는 과정을 반복시킨 후 출력해주면 됩니다.

 

실제 구현은 아래와 같습니다.

import sys
import math

N = int(sys.stdin.readline().rstrip())
k = int(math.log2(N//3))
# print(N,k)

init_star = ['  *  ', ' * * ', '*****']

def make_star(before_star):
    bottom_len = len(before_star[0])
    tmp = bottom_len//2 + 1

    new_star = list(map(lambda x : ' '*tmp+x+' '*tmp, before_star))
    for e in before_star:
        new_star.append(e + ' '+ e)

    return new_star

tmp = init_star
for _ in range(k):
    tmp = make_star(tmp)

for e in tmp:
    print(e)