BOJ-2447 별 찍기-10 Swift

문제

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***
* *
***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

내가 푼 풀이

- 재귀호출로 위 패턴을 주어진 N만큼 호출하는건 알겠는데... 규칙을 찾기 어려웠다.

- 다른사람의 풀이를 참고했다. 해당 문제는 분할정복기법이다.

N = 3일때, 가운데를 제외하고 8군데를 그린다.

N = 9일때, N=3일때의 경우를 8군데 그린다.

N = 27일때, N=9일때의 경우를 8군데 그린다. -> N= 3일때의 경우를 64군데 그리면된다.

이를 재귀호출해주면 되는데 규칙은 가운데를 비우는것이다.

 

0,0	0,1	0,2
1,0	1,1	1,2
2,0	2,1	2,2

N=3일때 [1, 1] 을 제외한 8군데를 그린다.

이는 x % 3 = 1, y % 3 = 1 이 된다는것이다.

 

N=9일때 위 세칸을 보자

0,0	0,1	0,2	0,3	0,4	0,5	0,6	0,7	0,8
1,0	1,1	1,2	1,3	1,4	1,5	1,6	1,7	1,8
2,0	2,1	2,2	2,3	2,4	2,5	2,6	2,7	2,8

공백인 위치는 [1, 1], [1, 4], [1,7] 이 된다.

첫번째  [1, 1]: x % 3 = 1, y % 3 = 1

두번째 [1, 4]: x %3 = 1, y % 3 = 1

세번째 [1, 7]: x %3 = 1, y % 3 = 1 가 된다.

 

문제는 N = 9일때의 중간 공백이다.

중간공백의 좌표는 [3, 3], [3, 4] [3, 5] 등 9개가 있지만, 3 % 3 = 0이 된다.

그래서 위의 규칙과 같이 만들어 재귀호출을 하기 위해 왼쪽값을 3보다 작은값으로 만든다.

-> 3 / 3 % 3 = 1형식으로 만든다.

또한 N이 9를 넘어간다면  9 /3 = 3 이되고, 3%3은 0이 되므로 위의 규칙과 맞지않는다.

따라서 나눗셈의 오른쪽값은 왼쪽값보다 크거나 같아야 3보다 작은값으로 나뉘어 3으로 나눠도 0이되지않는다.

 

-> 재귀호출할때마다 N으로 나누어 0이나오면 N을 3으로 나누어 재귀호출한다.

 

이를 코드로 구현하면 다음과 같다.

import Foundation

// 입력받기
var N = Int(readLine()!)!
var out = ""

// 그리기함수
// a / b 일때 b가 a보다 크면 0이다.
// 그래서 b를 3으로 나누고 다시 재귀호출
func draw(x: Int, y: Int, num: Int) {
    if x / num % 3 == 1 && y / num % 3 == 1 {
        out += " "
    } else {
        if num / 3 == 0 {
            out += "*"
        } else {
            draw(x: x, y: y, num: num/3)
        }
    }
}

for i in 0..<N {
    for j in 0..<N {
        draw(x: i, y: j, num: N)
    }
    out += "\n"
}
print(out)