백준 algorithm study python divide and conquery

파이썬 알고리즘 : 별 찍기 - 10

분할정복

2024년 5월 6일 알고리즘 문제풀이

문제

난이도

골드 5

코드

길이가 3인 정사각형에서 가운데만 비어있는 형태로 반복하여 쌓이게 된다. 정사각형을 9등분하여 가운데에만 제외하고 8개를 복사해준다고 생각했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import sys

n = int(sys.stdin.readline())
board = [[' ' for _ in range(n)] for _ in range(n)]

# 재귀함수 정의
def main(num:int):
    # 사각형이 최소크기면
    if num == 3:
        for i in range(3):
            for j in range(3):
                # 가운데(좌표 1,1)를 제외하고 *을 그려준다.
                if i != 1 or j != 1:
                    board[i][j] = '*'
        return
    
    # 3등분하여 재귀를 반복
    p = num//3
    main(p)

    for i in range(0, num, p):
        for j in range(0, num, p):
            # 가운데가 아닐 때를 제외하곤 똑같은 모양을 넣어준다.
            if i != p or j != p:
                for x in range(p):
                    board[i+x][j:j+p] = board[x][:p]

# 함수 실행
main(n)

# 결과 출력
for i in range(n):
    for j in range(n):
        print(board[i][j], end='')
    print()

출처 : TaxFree

CATALOG
    algorithm