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

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

2448번: 별 찍기 - 11

---

---

문제 분석

별 찍기 문제는 재귀를 활용하면 쉽게 풀 수 있다.

재귀를 하기 위해서는 기준점과 재귀의 기준이 필요하다.

여기서는 시작점과 길이를 기준으로 재귀를 진행한다.

 

출력을 보면 높이가 3인 작은 삼각형이 3번 반복해서 큰 삼각형을 만들고

또 그 삼각형 3개가 모여 하나의 삼각형을 이룬다.

 

결론적으로 높이가 3일 때 삼각형을 만들어주면 쉽게 재귀를 진행할 수 있다.

처음 탐색을 할 경우,

총 길이 n을 탐색하고 n이 3이 될 때까지 2로 나누면서 길이를 비교한다.

이유는 n이

3 * 2^k이기 때문이다.

 

별을 찍기 위해서 공백으로 된 배열을 미리 선언해주는데, 이 때 배열은 n개의 행을 가지고 2 * n의 열을 가진다.(실제로는 2 * n - 1의 열을 가지지만 편한 계산을 위해 2 * n으로 계산한다.)

 

우선 기준점은 맨 첫 번째 열의 별의 위치를 기준으로 한다.이 기준점의 위치는 항상 (0, n - 1)의 위치를 갖게 된다.가장 중심점은 열의 총 길이의 절반이기 때문에 0번째부터 세는 인덱스를 포함하여 n - 1번째 열이 된다.

 

n이 3이 되었다면, 작은 삼각형을 만들어준다.

arr[x][y], arr[x + 1][y - 1], arr[x + 1][y + 1] = "*", "*", "*"
arr[x + 2][y - 2 : y + 3] = ["*"] * 5

(x, y)를 기준점으로 하고 현재 위치와 다음 줄에서는 전의 열, 후의 열을 별로 찍고

다다음줄은 별을 5개 찍어야 한다.

 

이렇게 되면 모든 별을 원하는대로 찍을 수 있다.

---

코드

n = int(input())

arr = [[" "] * 2 * n for _ in range(n)]


def star(x, y, n):
    if n == 3:
        arr[x][y], arr[x + 1][y - 1], arr[x + 1][y + 1] = "*", "*", "*"
        arr[x + 2][y - 2 : y + 3] = ["*"] * 5

    else:
        star(x, y, n // 2)
        star(x + n // 2, y - n // 2, n // 2)
        star(x + n // 2, y + n // 2, n // 2)


star(0, n - 1, n)

for i in range(n):
    print("".join(arr[i]))