[Python] 백준 2447번 - 별 찍기 - 10 (골드5)

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

2447번: 별 찍기 - 10

 

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 분할 정복
 - 재귀

문제

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***
* *
***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

출력

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

 

 

---

처음엔 문제를 보고 어떻게 풀어야 하나 아무 생각도 들지 않았다.

 

나는 재귀 문제가 약해서 도저히 생각나지 않앗는데 예시의 별모양들을 계속 보고 있다가 패턴을 파악해 버렸다.

 

크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다.

 

이 말 뜯을 이해하는게 핵심이다.

 

27의 패턴은 9x9의 정사각형을 9의 패턴으로 둘러싼 형태

 = 중앙의 9x9칸을 비운 8방향을 9의 패턴으로 둘러쌈

 = 9의 패턴은 3x3의 패턴으로 둘러쌈 (가운데 3x3을 비운 형태)

 

---

n = 3

n = 9일 때

 

9일때를 보면 가운데 3x3칸을 비운 나머지 8방향이 n=3일 때로 둘러싼 형태임을 볼 수 있다.

 

그러므로 n = 27일 때는

 

 

중앙 9x9칸을 비운 나머지 8방향이 n=9일 때로 둘러쌓인 형태임을 알 수 있다.

 

---

import sys
input = sys.stdin.readline

n = int(input())
star = [ ["*" for _ in range(n)] for _ in range(n)]
def recursive(n, m, i, j):
    if m == 3:
        star[i+1][j+1] = " "
        return
    else:
        k = int(m /3)
        for a in range(i+k, i+k*2):
            for b in range(j+k, j+k*2):
                star[a][b] = " "
        
        return recursive(n, m/3, i, j), recursive(n, m/3, i, j+k), recursive(n, m/3, i, j+k*2), recursive(n, m/3, i+k, j), recursive(n, m/3, i+k, j+2*k), recursive(n, m/3, i+k*2, j), recursive(n, m/3, i+k*2, j+k), recursive(n, m/3, i+k*2, j+k*2)
        #각 8방향으로 3씩 나눈 값과, 각 좌표의 시작 위치 8방향을 뿌려준다.

recursive(n, n, 0, 0) #n: 주어진 값, m: 3씩 나눠질 값, i/j: 나눠진 방향의 (0, 0) 좌표 위치
for i in range(n):
    for j in range(n):
        print(star[i][j], end='')
    print()