[python] 별 찍기 - 11 (Baekjoon, 2448)

문제(Link) : https://www.acmicpc.net/problem/2448

백준 온라인 저지에 있는 분할정복 문제이다. 백준 기본 별 찍기 문제 11단계로, 분할정복을 사용해서 재귀 호출로 별을 찍는다.

N 이라는 수가 주어지면 첫째 줄부터 N번째 줄까지 별을 출력하는데, 출력된 결과를 2차원 배열로 나타내면 높이는 N이라는 것을 알 수 있지만 가로의 길이는 바로 알 수 없었다.

위 이미지는 N이 24일때의 출력 화면이다. 처음엔 결과가 정삼각형인 줄 알았지만, 생각해보니 아래면과 옆면의 길이가 같지 않은 그냥 이등변 삼각형이었다(하하).

이렇게 이런저런 생각을 많이 했지만 결국 문제를 해결하는데에는 필요없는 생각들이었고, 출력 모양 반복의 규칙을 찾아 재귀함수를 호출하는 방식이었다.

별이 찍힌 삼각형 중, 가장 작은 단위는 높이가 3일 때의 모양이었다. 그래서 재귀 함수 안에 종료 조건으로 n == 3이라는 조건을 주었다. 구현한 재귀 함수인 print_star()의 인자로는 삼각형의 꼭짓점이 시작하는 좌표(x, y)와 삼각형의 높이 n을 주어 호출하였다.

def print_star(x, y, n):
    if n == 3:
        ans[x][y] = '*'
        ans[x+1][y-1] = ans[x+1][y+1] = '*'
        for i in range(-2, 3):
            ans[x+2][y+i] = '*'
    else:
        nn = n // 2
        print_star(x, y, nn)
        print_star(x+nn, y-nn, nn)
        print_star(x+nn, y+nn, nn)


N = int(input())
ans = [[' '] * 2 * N for _ in range(N)]

print_star(0, N-1, N)
for row in ans:
    print("".join(row))