[BOJ] 16895 님 게임 3 - P4

문제풀이

1. 각각의 돌 더미들의 그런디 값을 xor한 값을 G라 했을때, G가 0이면 답은 0이다.
2. G가 0이 아닐 때, 각각의 돌 더미의 개수를 낮춰가며 새로운 그런디 값 G'를 만들고, 이 값이 0인 경우의 수를 카운팅 한다.

---

주의사항

---

소요시간

20분

---

package 백준.Platinum.P4.p16895_님게임3

fun main() {
    val N = readln().toInt()
    val pArr = readln().split(" ").map(String::toInt)
    fun result(): Int {
        val G = pArr.reduce { acc, i -> acc xor i }
        if (G == 0) return 0
        var result = 0
        for (i in 0 until N) {
            val nextG = G xor pArr[i]
            for (j in 0..pArr[i]) {
                if ((nextG xor j) == 0) result++
            }
        }
        return result
    }
    println(result())
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P4/p16895_%EB%8B%98%EA%B2%8C%EC%9E%843/p16895_%EB%8B%98%EA%B2%8C%EC%9E%843.kt

---

문제링크

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