[백준] 2447 별 찍기

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

2447번: 별 찍기 - 10

N = int(input())

star = '*'

star_list = [[' ' for i in range(N)] for i in range(N)]

def stars(N, x, y):
    if N == 1:
        star_list[x][y] = '*'
    else:
        N = N // 3
        for i in range(3):
            for j in range(3):
                if i != 1 or j != 1:
                    stars(N, x + N * i, y + N * j)
                        

stars(N, 0, 0)

for i in star_list:
    print(''.join(i))

이번 문제는 재귀 함수 중 별찍기 문제였다.

 

재귀를 원래 잘 못해서 한참 걸렸다. 겨우 풀어냈지만 시간초과가 걸려 그 문제를 해결하기 위해 또 한참 걸렸다.

 

우선 생각해낸 방식은 다음과 같다. 리스트안에 빈 문자열을 만들어 주고 가운데만 뚫어주는 것을 반복했다.

 

그림을 보고 규칙을 찾아보면

저 네모 친 모양이 반복되며 가운데만 비우는 것을 알 수 있다. N이 27이라고 하면 위의 9짜리 그림을 가운데만 비우고 8번 채우면 되는 것이다.

 

원리는 간단했지만 코드로 짜는것이 문제였다.

 

stars라는 재귀 함수를 만든 후 N이 1이되면 *로 바꿔준다.

 

만약 N이 1이 아니라면 3으로 나눠준 후 for문을 돌며 함수를 반복한다.

 

N이 9일때를 예를들어보면

 

(3, 0, 0) - (1, 0, 0), (1, 0, 1), (1, 0, 2), (1, 1, 0) ...

(3, 0, 3) - (1, 0, 3), (1, 0, 4), (1, 0, 5)...

(3, 0, 6) - ...

(3, 3, 0)

(3, 3, 3) - i, j가 1, 1이기 때문에 돌지 않아 N == 9일때의 가운데가 비게 된다.

(3, 3, 6)

(3, 6, 0)

(3, 6, 3)

(3, 6, 6)

순으로 돌아가며 *을 채운다.

 

시간초과를 해결하기 위해 x, y list를 따로 만들어 x, y를 담아준 후 이미 들어가있는 것에 대해서는 재귀를 안돌리는 방식을 사용하려 했으나 직접 써보면서 해보니 겹치는 것이 나올 수가 없었다.

 

그래서 문제가 뭘까 생각해봤는데

 

    if N == 1:
        star_list[x][y] = '*'

이 부분이 문제였다. 처음에는 N == 0 으로 작성했는데 왜냐하면 1일때나 0일때나 그게 그거아닌가? 생각했기 때문이다. 하지만 한참 생각해보니 N == 0 이 된다면 1일때가 한번 더 도는것과 다를것이 없기 때문에 for문으로 인해 9번이나 더 돌게 된다. 시간이 9배로 걸리기 때문에 시간초과가 생기고 중복이 생겼던 것이다.

 

오래 걸렸지만 문제를 해결해서 기분이 좋다