[백준] 2448번 별 찍기 11 - Python / 알고리즘 중급 1/3 - 분할 정복 (연습)

---

---

---

💡 문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수)

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

---

💭 접근

먼저 삼각형의 밑변 w와 삼각형의 높이 h를 구해준다.

w = int(n / 3 * 5 + n / 3 - 1)
h = n

이후 마지막 삼각형이 들어가게될 빈 리스트를 생성해준다.

star = [[' ' for _ in range(w)] for _ in range(h)]

이제 기준이 될 가장 작은 삼각형을 그려준다

star[0][w//2] = '*'
star[1][w//2 - 1] = star[1][w//2 + 1] = '*'
for i in range(-2, 3):
    star[2][w//2 + i] = '*'

이렇게 되면 일단 아래와 같은 가장 작은 삼각형이 리스트에 담기게 된다.

  *
 * *
*****

이제 위 삼각형을 사용해서 높이 n인 삼각형을 그려줄 것인데, 다음과 같은 원리로 동작한다.

def draw_star(iter):
    for i in range(iter):
        for j in range(w):
            if star[i][j] == '*':
                star[i + iter][j - iter] = '*'
                star[i + iter][j + iter] = '*'

    if iter * 2 == h:
        return

    draw_star(iter * 2)

1. 현재 그려져있는 삼각형을 순회하며 star[i][j]에서 *을 만날 경우,
   star[i + 삼각형의 높이][j ± 삼각형의 높이]도 *로 채운다.
2. 위 작업을 현재 삼각형의 높이가 목표 높이의 절반이 될때까지 반복한다.
   (만약 입력 n이 24이고 iter가 12라면 이미 아래에 12만큼 채웠기 때문)

위 작업을 그림으로 나타내면 아래와 같다.

ex) n = 6

   *         *           *           *             *             *
  * *       * *         * *         * *           * *           * *
 ***** ->  *****  ->   *****  ->   *****   ->    *****   ->    *****   -> ...
          *     *     *     *     *     *       *     *       *     *
                     *     *     * *   * *     * *   * *     * *   * *
                                              *     *       **    **

---

📒 코드

def draw_star(iter):
    for i in range(iter):
        for j in range(w):
            if star[i][j] == '*':
                star[i + iter][j - iter] = '*'
                star[i + iter][j + iter] = '*'

    if iter * 2 == h:
        return

    draw_star(iter * 2)


n = int(input())
w = int(n / 3 * 5 + n / 3 - 1)
h = n
star = [[' ' for _ in range(w)] for _ in range(h)]
star[0][w//2] = '*'
star[1][w//2 - 1] = star[1][w//2 + 1] = '*'
for i in range(-2, 3):
    star[2][w//2 + i] = '*'

if h != 3:
    draw_star(3)

for i in range(h):
    print(*star[i], sep='')

---

💭 후기

문제를 풀 땐 몰랐는데 오늘 복습할 떄 다시 보니 이렇게 풀거면 굳이 재귀를 사용할 필요가 없었을 것같다는 생각이 들었다.. 다시 한번 풀어보자.

---

🔗 문제 출처

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

---