문제풀이
- 3 + 2k, 6 + 3k, 10 + 4k ... 와 같이 ((N - i번째 까지의 구간합) % i == 0) 이면 돌 더미를 i개로 분리할 수 있다. 이때의 그런디 값은 xor값의 구간합으로 구할 수 있다.
- N까지의 그런디값을 전처리 한다.
- G[N]이 0이면 -1 출력, 0이 아니면 다음 그런디 값이 0이 될 수 있는 가장 작은 돌 더미의 개수를 출력한다.
주의사항
소요시간
20분
package 백준.Platinum.P3.p16886_나누기게임
fun main() {
val N = readln().toInt()
val list = mutableListOf(0)
var sum = 0
for (i in 1..N) {
sum += i
if (sum > N) break
list.add(sum)
}
val G = IntArray(N + 1)
val sumG = IntArray(N + 1)
val selected = BooleanArray(20)
for (i in 1..N) {
selected.fill(false)
for (idx in 2 until list.size) {
val value = list[idx]
if (i < value) break
if ((i - value) % idx == 0) {
val start = 1 + (i - value) / idx
val end = start + idx - 1
selected[sumG[end] xor sumG[start - 1]] = true
}
}
G[i] = selected.indexOf(false)
sumG[i] = sumG[i - 1]
if (G[i] != 0) sumG[i] = sumG[i] xor G[i]
}
fun result(): Int {
if (G[N] != 0) {
for (idx in 2 until list.size) {
val value = list[idx]
if ((N - value) % idx == 0) {
val start = 1 + (N - value) / idx
val end = start + idx - 1
if ((sumG[end] xor sumG[start - 1]) == 0) return idx
}
}
}
return -1
}
println(result())
}