[백준 9단계] 2447 별찍기 (재귀, 중요)

🥕 [ 백준 2447 ] 별찍기

문제 링크

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

2447번: 별 찍기 - 10

 

🍒 문제 분석

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

 

N = 3 일 때,

***
* *
***

N = 27 일 때,

***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

🥑 코택님의 코드

import sys
sys.setrecursionlimit(10**6)

def star(N):
    if N == 1:
        return ['*']
    stars = star(N//3)
    L = []

    for s in stars:
        L.append(s*3)
    for s in stars:
        L.append(s+' '*(N//3)+s)
    for s in stars:
        L.append(s*3)
    return L

N = int(sys.stdin.readline().strip())
print('\n'.join(star(N)))

코테,"[백준] 2447 - 별 찍기 - 10 [Python(파이썬)]",티스토리(블로그),2021.01.26, URL. https://cotak.tistory.com/38

[백준] 2447 - 별 찍기 - 10 [Python(파이썬)]

 

코텍님 코드는 매우 직관적이며 이해하기 쉬웠다.

N//3 에서 '*' 이었던게 N에서 '***' 가 되는 식이다.

그리고 동시에 매 N 마다 추가되는 빈칸에 대하여 잘 정리해 놓았다.

 

눈으로 봤을 때 직관적으로 문제를 파악하지 못했을 땐 이렇게 풀기는 어려울 것 같다.

그러나 이런 문제에 익숙해지면 또 그때 가서는 풀지 않을까.

 

 

 

🍓 내 해결 과정

내 코드는 시간 초과가 떴다. VS CODE를 돌렸을 때는 정상으로 돌아갔는데, 실제 제출 결과는 시간 초과 였다.

 

참고로 sys.setrecursionlimit(10**6) 은 너무 깊은 재귀에 들어가는걸 에러로 미리 알려준다고 한다.

재귀 문제를 풀 때, 내 VS CODE에 꼭 import 해야할 코드이다.

 

import sys
sys.setrecursionlimit(10 ** 6)

def starblink(N):
    if N == 3 :
        return [[],[1]]

    beforeblink = starblink(N//3)

    blinklist = [[],[]]
    blinklist[0] = beforeblink[0]+beforeblink[1]
    for i in range(len(blinklist[0])):
        blinklist[0].append(blinklist[0][i] + N//3)
        blinklist[0].append(blinklist[0][i] + 2*(N//3))

    blinklist[0] = list(set(sorted(blinklist[0])))

    blinklist[1] = [i for i in range(N//3,(N//3)*2)]

    return blinklist

N = int(input())
blinklist = starblink(N)

for i in range(N):
    for j in range(N):
        if i in blinklist[0] and j in blinklist[0]:
            print(' ',end='')
        elif i in blinklist[1] and j in blinklist[1]:
            print(' ',end='')
        else : print('*',end='')
    print()

 

🍉 깨달은 점 및 정리

1. 재귀 함수 문제를 풀 때는 다음의 코드를 꼭 쓰자.

import sys
sys.setrecursionlimit(10**6)

 

2. 리스트로 한 줄 한 줄의 프린트를 처리할 수 있다.

print('\n'.join(star(N))) 로 묶는다면 말이다.

 

3. 다음을 봐보자.

    for s in stars:              # 줄의 갯수가 늘어난다. (리스트 안의 요소 증가)
        L.append(s*3)         # 너비가 증가한다. ( 요소가 증가 )

 

4. 코택님의 풀이 1번은 눈으로 봐서 잘 이해가 안갔기 때문에 패스했다.

후에 돌아와서 이해가 되면 한번 정리해보자.

 

 

 

 

거의 뭐 외워버린 코드

import sys
sys.setrecursionlimit(10**6)

def star(N):
    if N ==1 :
        return ['*']
    before = star(N//3)
    l = []
    for i in before:
        l.append(3*i)
    for i in before:
        l.append(i+' '*(N//3)+i)
    for i in before:
        l.append(3*i)
    return l

N = int(input())
print('\n'.join(star(N)))