[Swift] 재귀 BOJ 2447 별 찍기

N=27인 경우
N=9인 경우가 3*3 형태로 되어있다
5번째 N=9인 경우는 모두 빈칸이다

---

N=9인 경우
N=3인 경우가 3*3 형태로 되어있다
5번째 N=3인 경우는 모두 빈칸이다

이를 이용해 분할 정복(Divide and Conquer)로 풀어보았다.

시도 1 - 가독성과 이해하기 좋다고 생각한 방법

하지만 시간 초과로 실패했다

import Foundation

var n = Int(readLine()!)!
var star_Prnt:[[Character]] = Array(repeating: Array(repeating: " ",count:n ), count: n)

func star_write(var N:Int, let i:Int, let j:Int,let blank:Bool) {
  var count = 0
  if(blank == true) {
    for blank_i in i...i+N-1 {
      for blank_j in j...j+N-1 {
        star_Prnt[blank_i][blank_j]=" "
        return
      }
    }
  }
  else if(N/3 == 0) { 
                 star_Prnt[i][j]="*"
                 return 
               }


  for xBlock in stride(from: i, to: i+N, by: N/3) {
    for yBlock in stride(from: j, to: j+N, by: N/3) {
      count += 1
      if(count==5){star_write(var: N/3, let: xBlock, let: yBlock, let: true)}
      else {star_write(var: N/3, let: xBlock, let: yBlock, let: false)}
    }
  }
}

star_write(var: n, let: 0, let: 0, let: false)
for a in 0..<n {
  for b in 0..<n {
    print(star_Prnt[a][b],terminator:"")
  }
  print()
}
  

---

시도 2 - 빈칸 점화식을 통한 해결 방식

N=9인 경우에서 빈칸의 좌표를 모두 나열하면

테두리 부분 빈칸

…...…………………………………
…..(1,1) ……(4,1)……(7,1)…..
…...…………………………………
.……………………………………..
…..(1,4)........…………(7,4)…..
…...…………………………………
.………………………………………
……(1,7)…….(4,7)……(7,7)….
…...………………………………….

테두리 부분 식: i % 3 == 1 && j % 3 == 1

---

중앙 부분 빈칸

(3,3) (4,3) (5,3)
(3,4) (4,4) (5,4)
(3,5) (4,5) (5,5)

중앙 부분 식: i/(N/3) == 1 (1또한 나머지가 1이다)

여기서 N/3은 재귀를 통해 N -> N/3으로 줄어들기 때문에 N으로 치환가능하다

---

이 점화식을 통합해보면

점화식

(i / n) % 3 == 1 && (j / n) % 3 == 1

import Foundation
let n = Int(String(readLine()!))!
var star = ""
for i in 0..<n {
    for j in 0..<n {
        starPrnt(n,i,j)
    }
    star += "\n"
}
print("\(star)")
func starPrnt(_ n: Int, _ i: Int, _ j: Int) {
    if (i / n) % 3 == 1 && (j / n) % 3 == 1 {
        star += " "
    }else {
        if n / 3 == 0 {
            star += "*"
        }else {
            starPrnt(n / 3, i, j)
        }
    }
}