[백준] 2448: 별 찍기 - 11

💻 백준 2448번: 별 찍기 - 11

• 문제 링크: https://www.acmicpc.net/problem/2448
• 알고리즘 분류: 재귀, 분할 정복

문제 소개 🧐

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. N은 항상 3×2^k 꼴의 수입니다.

입력 📝

• 첫째 줄에 N이 주어진다. (3, 6, 12, 24, 48, …), (0 ≤ k ≤ 10)

출력 📤

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

제한 ❌

• 시간 제한: 1초
• 메모리 제한: 256MB

---

재귀를 이용한 분할 정복 풀이 ✨

Idea

재귀적으로 처리해보자. 위 삼각, 아래는 삼각 + 삼각

주어진 별 패턴의 규칙성을 파악해보면, 큰 삼각형은 작은 삼각형 여러 개로 이루어진 재귀적인 구조임을 알 수 있다.
가장 작은 단위인 N=3 삼각형을 기본으로, N=6 삼각형은 위쪽에 N=3 삼각형 하나, 아래쪽에 N=3 삼각형 두 개가 있는 형태이다.

이러한 규칙에 따라, N 크기의 삼각형을 그리는 함수는 N/2 크기의 삼각형을 그리는 함수를 재귀적으로 호출하여 조합하는 방식으로 구현할 수 있다.

• 위쪽 삼각형: N/2 크기의 삼각형을 가져와 양 옆에 공백을 추가한다.
• 아래쪽 삼각형: N/2 크기의 삼각형 두 개를 공백 하나를 사이에 두고 나란히 붙인다.

Code

import sys
sys.setrecursionlimit(100000)

n = int(sys.stdin.readline().rstrip())

def star(x):
    if x == 3:
        return [
                "  *  ",
                " * * ",
                "*****"
               ]
    
    arr = star(x // 2)
    result = []
    
    # 위쪽 삼각형
    for line in arr:
        result.append(" " * (x // 2) + line + " " * (x // 2))
    # 아래쪽 두 삼각형
    for line in arr:
        result.append(line + " " + line)
    
    return result

print("\n".join(star(n)))

Result

• 결과: 성공! 🎉
• 재귀적인 구조를 파악하고 분할 정복으로 접근하여 문제를 해결할 수 있었다.

---

마무리 🤔

• 재귀적 패턴 파악: 복잡해 보이는 문제도 작은 단위로 나누어 규칙을 찾으면 재귀적으로 해결할 수 있는 경우가 많다. 이 문제는 분할 정복의 대표적인 예시이다.
• 출력 형식 처리: 재귀 함수가 리스트의 각 라인을 문자열로 반환하도록 하고, 마지막에 "\n".join()을 사용하여 전체를 출력하는 방식이 효율적이다.

프랙탈 구조와 유사한 문제로, 재귀 호출을 통해 큰 문제를 작은 문제로 나누어 해결하는 분할 정복의 힘을 느낄 수 있었다.

⁂