[BOJ] 10994. 별 찍기 - 19 (🥈, 구현)

문제

풀이

딱 봐도 뭔가 반복되는 느낌이다
그렇게 안 보이지만 그림의 사각형은 전부다 정사각형이다. 한 변의 길이와 시작되는 위치만 안다면 재귀든 반복문이든 사용해서 찍어주기만 하면 될 것 같다

문제는 안에서부터 밖으로 나가느냐, 밖에서부터 안으로 들어오느냐인데. 입력되는 숫자에 따라 최대 크기는 지정되어 있을 것 같으니 최대 크기의 배열을 정해놓고 밖에서부터 안으로 그리며 들어오는 게 편할 것 같았다.

우선 n번째 정사각형의 한 변의 길이는 4n-3이며 시작위치는 (0, 0)부터 시작해서 (2, 2), (4, 4)로 2단위씩 늘어나며 안으로 들어가게 된다. 밖에서부터 그려들어오기 때문에 n은 3부터 시작하게 되고, (0, 0)은 점점 커지면서 들어가니까 n과 i라는 변수를 둘 다 사용해준다. 하나는 사각형의 변의 길이를 결정하고 i는 시작위치를 결정한다.

일단 빨간색 사각형은 그릴 수 있는 최대의 정사각형 크기이다. (0, 0)부터 시작하는 한 변의 길이가 4*3-3인 정사각형이다. 가장 위와 아래의 변은 쭉 그려주고 그 외의 행은 처음과 마지막만 그려주면 된다.

그런 다음 n은 2가 되어야 하고, 시작위치는 (2, 2)가 되도록 i는 2를 증가시켜주면 된다.

N = int(input())
arr = [[' ']*(4*N-3) for _ in range(4*N-3)]

def recur_star(n, k):
    if not n:
        return 
    
    for c in range(4*n-3):
        arr[k][k+c] = '*'
        arr[k+4*n-4][k+c] = '*'

    for r in range(k+1, k+4*n-4):
        arr[r][k] = '*'
        arr[r][-1-k] = '*'

    recur_star(n-1, k+2)

recur_star(N, 0)
for row in arr:
    print(''.join(row))

나는 재귀로 풀었는데 아마 반복문으로도 풀릴 것 같다.
수학적으로 계산하면 훨씬 더 빠르게 푸는 방식도 있는 것 같지만 거기까지는..

후기

작년에 처음 알고리즘 시작하고 별 찍기 정복해보겠다고 야심차게 도전했다가 이 문제 보고 좌절했었는데 이번에는 보자마자 한 번에 풀렸다. 실력이란 게 안 느는 것 같은데 뭔가 늘긴 느나보다.. ㅎ