[백준][Python] 2448 별찍기(11)

실질적으로 별찍기(프렉탈 분할정복)

을 접한건 두번째다 첫번째는 감이 잘 안왔는데

이제는 슬슬 감이온다.

 

1. 입력값

2. 최소단위로 분할

3. 최소문제 해결

4. 더 큰문제 정복

5. 조합

 

정복시 그림이 잘 안그려질때는

실질적으로 뭐가 몇개 늘어났는지. 최소단위가 몇개 늘어나는지 잘 살펴보면 된다.

그리고 최소단위를 반복, 순회하면서 반복 덧셈, 곱셈을통해 확장시켜나가면 된다.

 

이 문제같은 경우 가장 작은 삼각형이 다음 차수에 밑에 2개 더 붙고

그다음은 그 큰 3개의 삼각형이 밑에 2개씩 더붙는다.

즉 이전 그림의 두배씩 아래쪽 배열에 추가된다고 생각하면 된다.

또 처음 들어갔던 배열도 " " 빈칸을 추가해줘야하는데 얼마나 추가해주냐면

실질적으로 늘어나는 3칸을 세어 3칸 -> 6칸 -> 12칸 즉 2의 배수씩 빈칸 더해주는 숫자도 늘어난다고 생각하면 된다.

한문제정도 더 풀어보면 유사유형도 풀 수 있을 것같다.

import sys
input = sys.stdin.readline


# 정복
def Conquer(shift):
    c = len(tri)                                                #최초 3 (즉 세로줄 수)
    for i in range(c):                                          #triangle 한줄씩 꺼냄.
        tri.append(tri[i] + tri[i])                             #tri.append(tri[i] + tri[i]) 3일때그림아래쪽에 바로 2개를 그림.
        tri[i] = ("   " * shift + tri[i] + "   " * shift)       #tri[i] = ("   "*shift + tri[i] + "   " * shift)
                                                                #아래쪽에 트리 두개 더한 그림을 그렸다면 원래 있던 그림에도 한줄씩 꺼내 " "공백을
                                                                #삐져나온만큼 더해준다.
                                                                #그럼 세로 3줄 -> 6줄 -> 12줄 -> 24줄 각 줄당 두줄씩 K번 더 그려지게된다.
#  입력
tri = ["  *   "," * *  ","***** "]                              # 삼각형 밑변끼리 붙지 않도록 오른쪽 한칸 띄어야함.
N = int(input())


# 분할

k=0
N = N//3
while N != 1 :
    N = N//2
    k +=1
# 조합
for i in range(k):
    Conquer(int(pow(2,i)))                                      #pow는 i승을 의미. 스페이스를 매k마다 2배씩 더 그려야 하기 때문.
for stars in tri:
    print(stars)