[백준] 2447번: 별찍기 - 10

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

2447번: 별 찍기 - 10

풀이

작은 패턴들이 더 큰 패턴을 이루는, 전형적인 재귀 문제이다.

N = int(input())
grid = [[' ']*N for _ in range(N)]

def recursion(n, x, y):
  if n == 1:
    return

  d = int(n/3)
  for i in range(3):
    for j in range(3):
      if not(i==1 and j==1):
        recursion(d, x+i*d, y+j*d)
        if d==1:
          global grid
          grid[x+i][y+j] = '*'

recursion(N, 0, 0)

for i in range(N):
  for j in range(N):
    print(grid[i][j], end='')
  print()

먼저, "*"를 담아두기 위해 NxN의 크기의 2차원 리스트를 만든다. 2차원 리스트 처음에 모두 공백 문자로 채워두고, recursion 함수를 돌아 필요한 좌표에 "*"을 채울 것이다.

 

recursion 함수는 정사각형의 한 면의 크기와, 좌측 상단 모서리의 좌표를 인수로 받는다. 면의 크기는 1/3로 쪼개어 9개의 작은 정사각형을 만들고, 가운데를 제외한 8개의 모서리 좌표는 recursion 함수를 재호출한다. 이런식으로 면의 크기를 쪼개다가 가장 기본 단위인 3x3이 되면, 2차원 배열의 모서리 좌표들에 "*"을 채운다. 정사각형의 크기가 1x1이 되면 return 문으로 재귀 호출을 중단한다.

 

 

참고로 채점은 통과했지만 시간 및 공간 효율이 매우 좋지 못하다.