문제
https://www.acmicpc.net/problem/2447
2447번: 별 찍기 - 10
재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이
www.acmicpc.net
시어핀스키 사각형을 별찍기로 구현하는 문제. 망델브로 아닌게 어디임
Reference
[백준] 2447 - 별 찍기 - 10 [Python(파이썬)]
문제 www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에..
cotak.tistory.com
일단 풀이가 두 개 있는데 2번이 쉽다고 함… 본인은 1번이 와닿아서 그거 참고함.
풀이
일단 풀기 전에 시어핀스키 사각형에 대해 보고 가자.
이놈이 시어핀스키 카펫(시어핀스키 사각형)이다.
시어핀스키 카펫은 프랙탈의 일종인데, 프랙탈은 그냥 똑같은 모양이 계속 반복되는 모양이다. 시어핀스키 카펫은 사각형을 9등분 한 다음 가운데를 지우고 그 사각형을 또 9등분해서 가운데 날리고 이런 식으로 반복되는 프랙탈의 일종. 이게 3차원이 되면 맹거 스펀지가 된다.
참고로 자매품으로 시어핀스키 삼각형도 있다. 이걸 코딩하라고 하면 개쌉고인물이 아닌 이상 힘들다.
일단 2번 풀이는 공간을 가로로 3등분하고 재귀함수를 통해 반복하는 형식이고(그래서 더 쉽다) 1번 풀이는 공간을 9등분 한 다음 5번째 공간을 공백으로 두는 방식이다. 그래서 배열이라는 개념이 나오는데… 어? 넘파이 있어야돼요? 아뇨 그러면 백준에서 빠꾸먹습니다…
arr1 = [['*' for i in range(3)] for j in range(3)]
for i in range(3):
for j in range(3):
print(arr1[i][j],end="")
print()넘파이 없어도 배열 만들 수는 있다. 저기서 3을 n으로 바꾸면 n*n으로 배열을 만드는 것도 가능하다. 물론 2차원 좌표 지정이나 슬라이싱도 넘파이랑 비슷하게 할 수 있다. (arr[i][j] 이런 식으로)
import sys
sys.setrecursionlimit(10**6)
def star(row):
div3 = row // 3
if row == 3:
arr[1] = ['*', ' ', '*']
arr[0][:3] = arr[2][:3] = ['*'] * 3
return
star(div3)
for i in range(0, row, div3):
for j in range(0, row, div3):
if i != div3 or j != div3:
for k in range(div3):
arr[i+k][j:j+div3] = arr[k][:div3]
n = int(input())
arr = [[' ' for _ in range(n)] for _ in range(n)]
star(n)
for i in range(n):
for j in range(n):
print(arr[i][j], end='')
print()row, 그러니까 입력한 값이 3일 때는 별별별 별 별 별별별이 출력된다. 엥? 근데 저 for문에 range는 뭔가요? 자, 입력을 9로 예시를 들면 0, 9, 3이 된다. (div3 = 입력값을 3으로 나눈 몫이니까 3) 그래서 0, 3, 6이 나오게 된다. 저기서 i가 3이 아니거나 j가 3이 아니면 들어가게 되는 for문의 범위가 3이 되어서 arr[i+k][j:j+3] = arr[k][:3]이 된다는 얘기. :3은 슬라이싱인데 0부터 할거라 0 생략한거라고 보면 된다. 그럼 여기서 i+k는 어떻게 될까?
위에서 9를 예시로 들었으니 9로 갑시다. 그러면
i, j = 0, 3, 6
k = 0, 1, 2(k는 div3, 즉 3까지)
i+k = 0, 1, 2, 3, 4, 5, 6, 7, 8
j+div3 = 0, 6, 9
그러면 저 배열에서 호출하게 되는 위치가 잡힐것이다. 배열의 [k][:div3]은 [0][:3], [1][:3], [2][:3]이다.
어? 그럼 둘다 3이면? 위에서 i랑 j가 둘 다 0, 3, 6이라고 했는데 저기서 3,3이면 가운데라 뭘 채울 게 없다. (뇌피셜 주의)
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
*** ****** ****** ****** ****** ****** ****** ****** ****** ***
* * * ** * * ** * * ** * * ** * * ** * * ** * * ** * * ** * * *
*** ****** ****** ****** ****** ****** ****** ****** ****** ***
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
********* ****************** ****************** *********
* ** ** * * ** ** ** ** ** * * ** ** ** ** ** * * ** ** *
********* ****************** ****************** *********
*** *** *** ****** *** *** ****** *** *** ***
* * * * * * * ** * * * * * * ** * * * * * * *
*** *** *** ****** *** *** ****** *** *** ***
********* ****************** ****************** *********
* ** ** * * ** ** ** ** ** * * ** ** ** ** ** * * ** ** *
********* ****************** ****************** *********
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
*** ****** ****** ****** ****** ****** ****** ****** ****** ***
* * * ** * * ** * * ** * * ** * * ** * * ** * * ** * * ** * * *
*** ****** ****** ****** ****** ****** ****** ****** ****** ***
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
*************************** ***************************
* ** ** ** ** ** ** ** ** * * ** ** ** ** ** ** ** ** *
*************************** ***************************
*** ****** ****** *** *** ****** ****** ***
* * * ** * * ** * * * * * * ** * * ** * * *
*** ****** ****** *** *** ****** ****** ***
*************************** ***************************
* ** ** ** ** ** ** ** ** * * ** ** ** ** ** ** ** ** *
*************************** ***************************
********* ********* ********* *********
* ** ** * * ** ** * * ** ** * * ** ** *
********* ********* ********* *********
*** *** *** *** *** *** *** ***
* * * * * * * * * * * * * * * *
*** *** *** *** *** *** *** ***
********* ********* ********* *********
* ** ** * * ** ** * * ** ** * * ** ** *
********* ********* ********* *********
*************************** ***************************
* ** ** ** ** ** ** ** ** * * ** ** ** ** ** ** ** ** *
*************************** ***************************
*** ****** ****** *** *** ****** ****** ***
* * * ** * * ** * * * * * * ** * * ** * * *
*** ****** ****** *** *** ****** ****** ***
*************************** ***************************
* ** ** ** ** ** ** ** ** * * ** ** ** ** ** ** ** ** *
*************************** ***************************
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
*** ****** ****** ****** ****** ****** ****** ****** ****** ***
* * * ** * * ** * * ** * * ** * * ** * * ** * * ** * * ** * * *
*** ****** ****** ****** ****** ****** ****** ****** ****** ***
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
********* ****************** ****************** *********
* ** ** * * ** ** ** ** ** * * ** ** ** ** ** * * ** ** *
********* ****************** ****************** *********
*** *** *** ****** *** *** ****** *** *** ***
* * * * * * * ** * * * * * * ** * * * * * * *
*** *** *** ****** *** *** ****** *** *** ***
********* ****************** ****************** *********
* ** ** * * ** ** ** ** ** * * ** ** ** ** ** * * ** ** *
********* ****************** ****************** *********
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
*** ****** ****** ****** ****** ****** ****** ****** ****** ***
* * * ** * * ** * * ** * * ** * * ** * * ** * * ** * * ** * * *
*** ****** ****** ****** ****** ****** ****** ****** ****** ***
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************이게 해당 코드로 81에 대해 돌린 결과이다.
*********
* ** ** *
*********
*** ***
* * * *
*** ***
*********
* ** ** *
*********9는 이런 식. 얘는 입력값에 대한 처리를 하고 입력값을 3으로 나눈걸 호출 호출 호출 하다가 최종 값이 3이 되면 별별별 별 별 별별별 부른다.
준비물: 얼굴 아니
'BOJ > [BOJ] Python' 카테고리의 다른 글
| 백준 11729번 풀이 (0) | 2022.08.19 |
|---|---|
| 백준 2477번 풀이 (0) | 2022.08.19 |
| 백준 17478번 풀이 (0) | 2022.08.19 |
| 백준 4153번 풀이 (0) | 2022.08.19 |
| 백준 1002번 풀이 (0) | 2022.08.19 |