[BOJ] 2448번 별 찍기 - 11

[BOJ] 2448번 별 찍기 - 11 문제

까다로운 재귀 문제다. 다만 푸는 방법을 파훼하면 급격히 쉬워지기에 그 방법을 알아보자.

---

우리의 목표는 피라미드 모양의 별을 보이는 패턴대로 찍는 것이다. 빈칸까지 붙어있으니 정말이지 어려워 보인다.

일단 출력 예시를 자세히 보면 빈칸이 앞에만 있는 것이 아니라 뒤에도 붙어있음을 생각해서 풀어야 한다. 이 때문에 PE(Print Error, 출력 형식 오류)가 생길 수 있으니 꼭 주의하자.

이 문제는 양 옆으로 붙은 빈칸이 있을 땐 굉장히 어려워 보이지만, 이 빈칸을 없애면 문제가 급격하게 쉬워진다.

$N$이 3 / 6 / 12 / 24일 때를 따로따로 보자.

# N == 3:
*
* *
*****

# N == 6:
*
* *
*****
*     *
* *   * *
***** *****

# N == 12:
*
* *
*****
*     *
* *   * *
***** *****
*           *
* *         * *
*****       *****
*     *     *     *
* *   * *   * *   * *
***** ***** ***** *****

# N == 24:
*
* *
*****
*     *
* *   * *
***** *****
*           *
* *         * *
*****       *****
*     *     *     *
* *   * *   * *   * *
***** ***** ***** *****
*                       *
* *                     * *
*****                   *****
*     *                 *     *
* *   * *               * *   * *
***** *****             ***** *****
*           *           *           *
* *         * *         * *         * *
*****       *****       *****       *****
*     *     *     *     *     *     *     *
* *   * *   * *   * *   * *   * *   * *   * *
***** ***** ***** ***** ***** ***** ***** *****

 

패턴이 바로 보이는 것을 알 수 있다!

일단 이 문제는 재귀를 해야하기 때문에 첫 항을 설정해줘야 하고, 이는 $N$이 3일 때가 된다.

3 이후의 항들을 $K$라고 할 때, $K$항은 $K-1$에서의 항과 해당 항에서 찍히는 모든 문장이 빈칸을 사이에 두고 양 옆에 있는 문장이 연이어 찍히는 것을 볼 수 있다. 그리고 빈칸의 크기는 해당 $N$을 이용하고, 그 크기는 $N-1-2\times (st{r}^{\prime }slinenum)$이 된다. 이 문장들이 이해가 안된다면 위의 결과들을 직접 보면서 곰곰히 생각해보면 된다. 그래도 모르겠다면 재귀를 다시 공부하면 된다.

이를 코드로 그대로 옮기고, 마지막에 양 옆에 빈칸을 붙이면 이 문제를 풀게 된다.

import sys

def star_print(n):
    if n == 3:
        star.append('*')
        star.append('* *')
        star.append('*****')
        return

    else:
        star_print(n//2)
        temp_star = list()
        for i in range(len(star)):
            temp_star.append(star[i]+' '*(n-1-2*i)+star[i])
        star.extend(temp_star)

if __name__ == '__main__':
    N = int(sys.stdin.readline().rstrip())
    star = list()
    star_print(N)
	
    for i in range(len(star)):
        print(' '*(N-1-i) + star[i] + ' '*(N-1-i))

 

재귀 함수에서 $N$이 3 초과일 경우엔 2를 나눈 값을 넣어 재귀시킨다. $N$이 3이 되었을 땐 첫 항을 돌려주고, 차례대로 재귀 패턴에 맞게 별을 찍어주면 된다.

여기서 iterator의 for문을 안전하게 쓰고자 temp라는 list에 추가될 별 문장들을 저장하고, 이를 기존 star라는 list에 extend를 하여 연장시키는 방법으로 접근했다. 마지막엔 빈칸을 문제 출력에 맞게 넣었다.