2447 별 찍기 _python

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

2447번: 별 찍기 - 10

 

와...결과 딱 보자말자 문제에 벽을 느꼈다. 실버임에도 불구하고 출력이 패턴은 보이나, 너무 복잡한 그림이였다.

문제를 읽어보니 재귀로 풀기 좋은문제고, 패턴에서 가운데만 공백으로 그리라는 문제였다.

"(N/3)*(N/3)을 N/3이 둘러쌌다"는 글에서 연산은 N//3으로 재귀를 돌리면 문제가 풀린다는걸 알 수 있다.

 

시도1

N*N크기의 배열을 먼저 선언해서 저장을 해뒀다가 최종적으로 출력하도록 생각을 했다.

그리고 배열에 [x][y]를 연산하도록 재귀함수에 i,j라는 매개변수와 N을 추가했고, 공백인지 *인지 확인하도록 drawable을 추가했다.

사실 이때 매개변수가 4개나 되서 시간초과가 날거라고 생각했지만, 끝까지 생각난대로 풀어봤다.

반복문으로 함수를 다시 호출할때, [i][j]가 몇번째 인덱스를 가르키는지 연산을 해서 넘겨줬다.

import sys
input = sys.stdin.readline

N = int(input())

#문제 요약
# 각 3의 k승에 대해 3x3의 크기로 쪼개어 봤을 때, 가운데에 있는 (1,1)을 공백으로 처리.
# (x,y)로 봤을때 x==1, y==1인 경우 공백, 나머지는 *로 출력.
arr=[[0 for i in range(N)] for i in range(N)]

def recursion(i, j, N, drawable):
    global arr
    if N == 1:
        if drawable:
            arr[i][j] = "*"
        else:
            arr[i][j] = " "
    else:
        for x in range(3):
            for y in range(3):
                if x==1 and y==1:
                    recursion(i+(x*N//3),j+(y*N//3) ,N//3, False)
                else:
                    if drawable:
                        recursion(i+(x*N//3),j+(y*N//3) ,N//3, True)
                    else:
                        recursion(i+(x*N//3),j+(y*N//3) ,N//3, False)
            

recursion(0, 0, N, True)
for i in range(N):
    for j in range(N):
        print(arr[i][j],end="")
    print()

 

 

이렇게 제출했는데 시간이 69000KB에 4850ms로 아슬아슬하게 통과.

다른 사람들의 채점을 봤는데 40000KB에 80ms가 있었다.

코드도 엄청 간략하고, 쉽게 풀었는데 메모리와 시간이 비교안될정도로 차이난다.

 

시도2

import sys
sys.setrecursionlimit(10**6)

N = int(input())

def append_star(N):

    if N==1:
        return "*"

    else:
        stars = append_star(N//3)
        end = []

        for star in stars:  #배열의 한줄씩 
            end.append(star*3)    #각 행의 3배 길이를 배열에 넣음.
        for star in stars:
            end.append(star + " "*(N//3) + star)  #stars도 N//3길이, 공백도 N//3길이
        for star in stars:
            end.append(star*3)
        
        return end

print("\n".join(append_star(N))) #한줄마다 줄내림

다른 블로그들을 찾아보며 풀었는데, 이해하기는 쉬운 코드였다.

하지만 이해는 되더라도 다시 쓰려고하니까 너무 어려웠다.

 

else에서 배열을 담아두고 각 배열을 행*3의 크기를 만들어서 배열의 길이만큼 반복한다.

이때, 중앙에는  공백이 필요하므로 중앙 1/3지점에선 *이 아닌 공백을 넣도록 진행하고,

다 만들어진 모양을 return해준다.

 

코드를 천천히 읽어보면서 N이 3일때, 9일때, 27일때 어떻게 돌아가는지 생각하면서 코드를 읽어보면 이해가 잘되더라.