Kotlin 🍬 백준 15단계 :: 13909 번

창문 닫기

문제   |

  서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다.  2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.

  예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,

1. 1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)
2. 2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)
3. 3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)

  결과적으로 마지막에 열려 있는 창문의 개수는 1개 이다.

입력   |

  첫 번째 줄에는 창문의 개수와 사람의 수 N(1 ≤ N ≤ 2,100,000,000)이 주어진다.

 

출력   |

  마지막에 열려 있는 창문의 개수를 출력한다.

 

 

풀이  |

  창문 상태를 저장하는 boolean array를 생성한다. (닫힌 상태면 false, 열린 상태면 true)

  1부터 N 까지 돌면서 해당 값의 배수 값으로 true면 false로, false면 true로 상태를 변경해주고 최종적으로 true인 상태의 값의 갯수를 구한다. 

 

 

답안  |

fun main() {
    val N = readLine()!!.toInt()

    val windows = BooleanArray(N) { false }

    for (person in 1..N) {
        for (i in person - 1 until N step person) {
            windows[i] = !windows[i]
        }
    }

    val count = windows.count { it }

    print(count)
}

 

^ 그런데 NZEC이라는 런타임 에러가 발생했다.

 

Exit code가 0이 아닌게 뭘까...

 

아무튼 다른 방식으로 접근해야 했다.

짝수 개의 약수를 지니면 최종적으로 닫힘상태이므로, 홀수 개의 약수를 지는 수의 갯수를 구하면 된다. 홀수 개의 약수를 지닌 수는 제곱근이기 때문에 N 이하의 제곱근의 수를 구하면 된다.

fun main() {
    val N = readLine()!!.toInt()

    var count = 0
    var i = 1

    while (i * i <= N) {
        count++
        i++
    }

    print(count)
}