[Python] 백준 2448번: 별 찍기 - 11

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

2448번: 별 찍기 - 11

 

 

문제를 보면 N번째 줄까지 별을 출력하고, N은 항상 3x2^k의 수입니다.

 

N = 6 은 위, 대각왼쪽아래, 대각오른쪽아래가 N = 3 이 반복된 것을 볼수있습니다. 

N = 12 은 위, 대각왼쪽아래, 대각오른쪽아래가 N = 6 이 반복된 것을 볼수있습니다.

 

이렇게 N은, N / 2가 위, 대각왼쪽아래, 대각오른쪽아래로 만들어 진것입니다.

그럼 이 모든 값을 좌표로 저장하기 위해 2차원 배열을 만들고, 세로는 N개만큼, 가로는 2*N - 1만큼 만들어 줍니다.

이제 좌표에서 공식을 도출하면, N = 12 인 경우를 예로 들겠습니다.  맨위 꼭짓점 기준으로 3등분 하겠습니다.

3등분 한 조각들과 좌표들이 나열 됐습니다. 그럼 다시 이 좌표들을 N/2로 쪼개고 N이 3이될때까지 분할해줍니다. N = 3이면 중간이 빈 삼각형을 좌표에 넣어줍니다.

 

공식을 도출하면 위와 같은 식이 나옵니다. 이제 코드 구현 하겠습니다.

M = int(input())
star = [[' ' for _ in range(M*2)] for _ in range(M)]

def go(x, y, n):
    if n <= 3:
        for i in range(3):
            for j in range(i+1):
                star[x+i][y+j] = star[x+i][y-j] = '*'
        star[x+1][y] = ' '
        return
    m = n // 2
    go(x, y, m)
    go(x+m, y-m, m)
    go(x+m, y+m, m)

go(0, M-1, M)

for i in range(M):
    print("".join(star[i]))