[Kotlin] 백준 6523 : 요세푸스 한 번 더!

문제 링크 : https://www.acmicpc.net/problem/6523

문제 해설

일종의 구현 문제. 따로 특별한 알고리즘이 필요하진 않다.

 

문제에서 각 사람들은 두번째에 걸렸을 때 술을 마시게 되고, 누구든 세 번 걸린다면 모두 집에 간다는 내용이 있다. 술을 마시지 않고 집으로 가는 사람의 수를 출력해야 하기 때문에 누군가 두번째 걸렸을 때 술을 마신 사람의 수를 더하고, 세번째 걸린다면 해당 테스트 케이스를 종료하면 된다.

 

각 사람들이 걸린 횟수를 기록하기 위해 HashMap을 사용한다. 정수배열을 사용해서 기록할 수도 있겠으나, 크기가 최대 10억인 정수배열을 선언하게 되어 어마어마한 메모리를 차지하게 되는 문제가 있어서 사용할 수 없다.

 

현재 사람의 번호가 \(x\)일 때 다음 사람의 번호는 \(ax^2+b\mod N\)이 된다. 처음에는 \(x=0\)이기 때문에 다음 순서의 사람 번호는 \(b\)가 된다.

 

다만 \(ax^2+b\mod N\)를 구할 때 \(ax^2\)이 Long의 범위를 초과할 수 있기 때문에(ex. \(1,000,000,000\times 999,999,999^2\)) 모듈러 연산의 분배법칙을 활용하여 Long 범위를 초과하지 않도록 적절히 분배하면 된다.

 

지금까지 이야기한 내용을 코드로 나타내면 다음과 같다.

val count = HashMap<Int, Int>()
var drink = 0
var next = b
while (true) {
    count[next] = (count[next] ?: 0) + 1
    if (count[next] == 3) break
    if (count[next] == 2) drink++
    next = ((((a.toLong() * next) % n) * next + b) % n).toInt()
}

여기에 추가적으로 문제의 메모리 제한이 적기 때문에 각 테스트 케이스가 종료될 때마다 가비지 컬렉션을 수동으로 실행했다. 가비지 컬렉션을 실행하지 않으면 메모리 초과가 발생하고, 메모리 초과를 방지하기 위해 횟수를 Int 타입 대신 Byte 타입으로 계산할 수도 있으나 메모리의 사용량이 약 5.7배나 많기 때문이다.

 

Code

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    lateinit var input: String
    while (readLine().also { input = it } != "0") {
        val (n, a, b) = StringTokenizer(input).run { IntArray(3) { nextToken().toInt() } }
        val count = HashMap<Int, Int>()
        var drink = 0
        var next = b
        while (true) {
            count[next] = (count[next] ?: 0) + 1
            if (count[next] == 3) break
            if (count[next] == 2) drink++
            next = ((((a.toLong() * next) % n) * next + b) % n).toInt()
        }
        bw.write("${n - drink}")
        bw.newLine()
        System.gc()
    }
    bw.close()
}

여담

사실 매 테스트 케이스마다 가비지 컬렉션을 실행하지 않고 HashMap의 value 타입을 Byte 타입으로 하면 메모리 초과를 방지할 수 있으나 시간은 약 18.3%만 절약되는 것에 비해 메모리 사용량이 5.7배나 많아서 비효율적이라고 판단했다.

아래 제출이 가비지 컬렉션을 실행하지 않고 Byte 타입을 사용한 코드, 위 제출이 가비지 컬렉션을 실행한 코드이다.