Swift) 백준 2447번(분할정복)

요구능력 : 분할정복방법을 사용할 줄 아느냐..

코드설명 : 우선 빈 문자열을 선언하고 계속 추가한 이유를 말하자면 처음에는 프린트를 썻었는데 계속 시간초과가 나왔다.

프린트를 많이 쓸 수록 시간이 오래걸린다는걸 깨달았다!! 이렇게 하나 배우는구나..

우선, 분할정복알고리즘이라는걸 알고있어야 이 문제에 접근하기 쉽다.

이 문제에서 분할정복알고리즘이 필요한 이유는 작은 별모양과 같은 규칙을 가진 큰 별모양을 만드는 것이기 때문이다.

자, 이제 설명을 해보자면 n = 3 일 때를 봅시다.

n = 3

맨 왼쪽 위를 기준으로 (1,1)에 빈칸이있다.

이제 n = 9 일 때를 봅시다.

n = 9

뭔가 상당히 비슷합니다.

이제 n = 27 일 때를 봅시다.

n = 27

이제 공통점을 아시겠나요?

그림을 자세히 보시면 n = 27일 때는 n = 9 일 때를 8번 호출하고, n = 9 일 때는 n = 3을 8번 호출합니다.

여기서 생각해야하는건 재귀함수를 써야한다는 것입니다. 왜? 똑같은걸 여러번 반복해서 호출해야하기 때문에

n = 27을 그려주려면 n = 9를 8번 호출해야되는데 이는, n = 3을 64번 호출해야된다는 소리입니다.

이제 재귀함수를 써야하는데 재귀함수를 쓰려면 규칙을 찾아야합니다.

n = 9 아니면 n = 27일 때의 그림을 보고 규칙을 찾아야됩니다. n = 3일 때는 재귀라고 할 것도 없이 모양 1개만 있기 때문에 여기서는 찾을 규칙이 없습니다. 저는 n = 9인 그림에서 규칙을 찾아보겠습니다.

 

 

n = 3 을 8번 그려줘야 합니다. 그럼 규칙을 찾아야겠죠. n = 3인 모양의 규칙부터 보면 (1, 1), (4,1) (7, 1), (1, 4), (7, 4) 이렇게 빈칸이 나옵니다.

이걸보고는 i % 3 == 1 && j % 3 == 1 이라는 규칙이 유추가 되죠?

이렇게 유추할 수 있는 이유는 위에서 설명했듯이 재귀함수를 사용해서 여러번 그려주려면 그려주기위한 규칙을 찾아야 된다고 생각하고 있기 때문에 찾을 수 있는겁니다.

현재까지는 n = 3만을 그려주기위한 규칙을 찾은겁니다.

이제 n이 27이되고 더 큰수가 되면 그려주기 위해서는 계속해서 변하는 수 n과 규칙을 연관지어야만 n을 쫓아서 그림이 그려질겁니다.

이걸 생각하고 규칙을 찾아봅시다.

위의 그림을 다시 한번보면 가운데에 비어있는곳의 좌표는 (3, 3) (3, 4) (3, 5) (4, 3) (4, 4) (4, 5) (5, 3) (5, 4) (5, 5) 입니다.

결국 지금 찾은좌표들은 공통적으로 (1,1)에 있는 것인데요. 이것을 일반화 해보려면 n = 3일 때의 x, y크기는 3이고 n = 9일 때의 x, y의 크기는 9라는걸 알아야합니다.

그럼 위에서 구한 규칙 i % 3 == 1 && j % 3 == 1 여기에서 좌표인 i와 y를 3으로 나누면되겠죠?

(i / 3) % 3 == 1 && (j / 3) % 3 == 1 이렇게 나옵니다.

위에서 말씀드렸듯이 n과 연관지어보면 (i / n) % 3 == 1 && (j / n) % 3 == 1 이라는 규칙성을 갖고있어야합니다.

엥? 현재 설명하고 있는 n은 9인데 왜 n을 넣나요? 위에선 3으로 넣지않나요? 라고 할 수 있습니다.

재귀함수를 사용해서 계속 n을 쪼개줄것이기 때문입니다.

(계속 쪼개주다보면, n = 9 일때의 공백은 3으로 나누어줄 때 표현되고, n = 27일때는 9로 나누어줄 때 표현된다.)

아래 코드를 보시면 조건에 맞으면 공백입니다. 그렇지 않았을 때 만약 n이 더이상 쪼개지지 않는다면 별을 출력합니다. 더 이상 쪼개지지 않을 때(n == 1 일 때) *을 출력하는 이유는 저도 오랜시간 찾아보고 고민했는데, https://st-lab.tistory.com/95 이곳에서 설명해 놓으신걸보고 이해했습니다. 제가 이해한대로 말씀드리자면, 어차피 n = 9, 27, ... 인것들 모두 n = 3의 형태로 별찍고 합친겁니다.

그런데 공백은 위에서 규칙 설명을 보시면 아시겠지만, n에 따라 다 틀립니다. 그래서 n이 더 이상 3으로 쪼개지지 않는다면 별을 출력하는겁니다.(참고로 3인이유는 문제에서도 나왔듯이 n이 3의k승 밖에 없기때문입니다.)

func printStar(_ n: Int, _ i: Int, _ j: Int) {
    if (i / n) % 3 == 1 && (j / n) % 3 == 1 {
        star += " "
    }else {
        if n / 3 == 0 {
            star += "*"
        }else {
            printStar(n / 3, i, j)
        }
    }
}

전체코드에서 i, j를 인수로 n까지 돌린이유는 가로세로 총사이즈가 n이기 때문입니다.

 

이해안가는부분 있으시면 댓글남겨주세요 ^^

 

후기 : 이런 유형은 처음 접해서 굉장히 고전했다.. 도저히 못풀겠어서 찾아봣는데 알고리즘을 푸는방법을 익혀야 풀 수있는 문제 처음보는데 맞추면 천재라고 인정해주고싶다.

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