[BOJ] 3596 크로스와 크로스 - P2

TaeGN·2024년 8월 17일

algorithm kotlin

BOJ Platinum Challenge

목록 보기

17/114

문제풀이

0 ~ n까지 Grundy Number를 구해서 승리 여부를 판단한다.

주의사항

어떤 지점에 x마크를 하면 양 옆으로 2칸은 더이상 마크 할 수 없는 지점과 다름 없다.

소요시간

20분

package 백준.Platinum.P2.p3596_크로스와크로스

import kotlin.math.max

fun main() {
    fun result(n: Int): Int {
        val G = IntArray(n + 1).apply { this[1] = 1 }
        val set = mutableSetOf<Int>()
        for (i in 1..n) {
            set.clear()
            for (j in 1..(i + 1) / 2) {
                set.add(G[max(0, j - 3)] xor G[max(0, i - j - 2)])
            }
            for (j in 0..n) {
                if (j !in set) {
                    G[i] = j
                    break
                }
            }
        }
        return if (G[n] > 0) 1 else 2
    }
    println(result(readln().toInt()))
}