[코딩테스트 문제] 열려 있는 보관함은 몇 개일까? (백준 13909: 창문 닫기)

문제

• 동일한 풀이의 문제: 백준 13909: 창문 닫기

어느 학교에 1부터 100까지 번호가 붙은 보관함이 한 줄로 늘어서 있다. 최초로 들어온 학생이 1번부터 100번까지 보관함의 문을 모두 열면서 나아갔다. 다음에 두 번째로 들어온 학생이 짝수 번째(=2의 배수 번호)의 보관함 문만 닫으면서 나아갔다. 다음에 세 번째 학생이 들어와 3의 배수 번호의 보관함 가운데 문이 열려 있는 것은 닫고, 닫혀 있는 것은 열면서 나아갔다 다음에 네 번째 학생이 들어와 4의 배수 번호의 보관함 가운데 문이 열려 있는 것은 닫고, 닫혀 있는 것은 열면서 나아갔다. 이와 같은 일이 n번째 학생까지 계속되었다. 그러면 n번째 학생이 지나간 뒤에 열려 있는 보관함은 모두 몇 개일까?

제한사항

n은 100,000,000이하의 자연수이다.

입출력 예

• n=2인 경우 결과는 1이다.
• n=5인 경우 결과는 2이다.

해답

맨 처음 학생이 지나간 뒤는 "열림•열림•열림•열림…",  2번째 학생이 지나간 뒤는'열림•닫힘•열림•닫 힘…" 하고 하나씩 생각해 나가는 것으로는 이 문제를 풀기 어렵습니다.

func solution﹖(_ n: Int) -> Int {
    var doorState: [Bool] = .init(repeating: false, count: n + 1)
    
    for i in 1...n {
        for j in i...n where j % i == 0 {
            doorState[j].toggle()
        }
    }
    
    return doorState.filter({ $0 }).count
}

이와 같이 접근하면 아래와 같은 솔루션(?)이 나오며 시간복잡도 O(n²)를 가지는데, 제한사항이 n = 100000000 (1억)이므로 만약 1억을 대입한다면 시간복잡도는 O(10¹⁶), 즉 1경이 나오기 때문에 시간을 매우 많이 초과합니다.

따라서 이 문제를 풀기 위해서는 어떤 법칙이 있는지 알아야 합니다.

먼저, 맨 처음 학생이 들어오기 전에는 문이 모두 닫혀 있습니다.

최종적으로 어떤 문이 열려 있기 위해서는 그 문을 거쳐간 학생의 수가 [홀수]일 때여야 합니다. 예를 들어 4번째 문을 열린 상태로 두기 위해서는 첫번째 학생이 문을 전부 열고, 두번째 학생이 문을 닫은 뒤 네번째 학생이 그 문을 다시 열어두면 4번째 문은 열려있게 됩니다. (세번째 학생은 3의 배수만 신경쓰므로 4번째 문은 그냥 지나간것이고, 이 학생은 카운트하지 않습니다.)

그 문을 거쳐간 학생의 수가 [짝수]인 경우에는 열렸다 닫히는 작업이 이루어지므로 최종적으로 문은 닫히게 됩니다.

• n=4 인 경우 4번째 문은 첫번째(홀수)가 지나가면 열리고, 두번째 학생(짝수)가 지나가면 닫힙니다.
• n=3 인 경우를 생각해봐도 3번째 문은 첫번째(홀수)가 지나가면 열리고, 세번째 학생(짝수)가 지나가면 닫힙니다.

여기서 규칙을 찾아보면

• 3번째 보관함의 문을 조작하는 것은 1번째와 3번째의 학생입니다. (구성원 짝수)
• 4번째의 보관함 문을 조작하는 것은 1번째, 2번째, 4번째의 학생입니다. (구성원 홀수)
• 5번째 보관함 문은 1번째와 5번째 학생입니다. (구성원 짝수)
• 6번째 보관함 문은 1•2•3•6번째 학생입니다. (구성원 짝수)

즉 n번째 문을 조작하는 것은 [n의 약수]번째 학생임을 알 수 있습니다.

• Swift: 약수(divisor) 구하기

위에서 본 것처럼, 2~6번째 보관함 중에서 최종적으로 열려있는 상태가 되는 [홀수]명에게 조작되는 것은 4번째 보관함뿐입니다. 그러면 4번째는 다른 수와 무엇이 다를까요?

일반적으로 어떤 수의 약수는 짝을 이루므로 짝수 개가 됩니다. (두 쌍을 곱하면 원래 수가 나옵니다.)

• 3이면 (1, 3)
• 5라면 (1, 5)
• 6이라면 (1, 6) (2, 3)
• 8이라면 (1, 8) (2, 4)

와 같은 식입니다.

그러나 4의 경우 (1, 4)는 짝이 되지만 2는 홀로 남았기 때문에 짝을 이루는 수는 없습니다. 4가 되기 위해서는 2를 제곱해야 합니다. 여기까지 이르면 벌써 예상이 될 것입니다. 4처럼 자연수를 제곱근으로 갖는 ‘제곱수(정사각수)’만이 홀수 개의 약수를 갖습니다.

• 9의 약수는 (1, 3, 9)
  • (1, 9)는 짝을 갖지만 3은 홀로 남았고 3은 9의 제곱근입니다.
• 16의 약수는 (1, 2, 4, 8, 16)
  • (1, 16) (2, 8)은 짝을 갖지만 4는 홀로 남았고 4는 16의 제곱근입니다.

정답을 구하려면 1부터 n까지의 범위에서 이런 제곱수가 몇 개인지 찾으면 됩니다.

• n = 100인 경우 [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]으로 제곱수는 총 10개
• n = 50인 경우 [1, 4, 9, 16, 25, 36, 49] 총 7개
• n = 95인 경우 [1, 4, 9, 16, 25, 36, 49, 64, 81] 총 9개
• n = 400인 경우 [1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400] 총 20개

n = 50인 경우 진행 상황

여기서 또한 특정한 규칙을 발견할 수 있습니다. n = 100이나 n = 400처럼 제곱수의 경우는 그 수의 제곱근이 1.부터 n까지의 제곱수의 개수가 되며, n = 50(=> 7.07), n = 95(=> 9.75) 처럼 제곱수가 아닌 경우에는 제곱근의 소수점을 버림한 값이 제곱수의 개수가 됩니다. 즉, 버림한 제곱근을 구하면 문제에서 원하는 정답이 나옵니다.

따라서 위의 문제는 아래와 같이 시간복잡도 O(1)로 줄여서 해결할 수 있습니다.

func solution(_ n: Int) -> Int {
    Int(sqrt(Double(n)))
}

출처

• <Newton> 수학 퍼즐 50 : 열려 있는 보관함은 몇 개일까?