[BOJ] 16877 핌버 - P3

문제풀이

1. 3000000까지의 피보나치 수열을 구한다.
2. 3000000번째 까지의 Grundy값을 전처리 한다.

---

주의사항

1. mex값을 구할 때 사용하는 Boolean배열의 크기는 최대 Grundy값의 크기로 설정하면 된다.

---

소요시간

40분

---

package 백준.Platinum.P3.p16877_핌버

const val MAX_P = 3000000
fun main() {
    val fibonacci = mutableListOf(1, 1)
    while (fibonacci.last() < MAX_P) {
        fibonacci.add(fibonacci.last() + fibonacci[fibonacci.size - 2])
    }
    val G = IntArray(MAX_P + 1)
    val selected = BooleanArray(fibonacci.size)
    for (i in 1..MAX_P) {
        selected.fill(false)
        for (num in fibonacci) {
            if (i - num < 0) break
            selected[G[i - num]] = true
        }
        G[i] = selected.indexOf(false)
    }
    val N = readln().toInt()
    val result = readln().split(" ").map(String::toInt).fold(0) { acc, i -> acc xor G[i] }
    println(if (result != 0) "koosaga" else "cubelover")
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P3/p16877_%ED%95%8C%EB%B2%84/p16877_%ED%95%8C%EB%B2%84.kt

---

문제링크

https://www.acmicpc.net/problem/16877

---

회고

시간 초과가 떠서 어떻게 시간을 줄일까 많은 고민을 하였다. mex값을 구할 때 사용하는 Boolean배열의 크기가 아무리 커도 fibonacci배열의 크기보다 클 필요가 없다는 것을 깨달았다.