#9655 돌 게임

문제

---

 

코드

---

fun main() {
    val n = readln().toInt()
    val winner = BooleanArray(1001)
    winner[1] = true; winner[3] = true
    for (i in 4..n) {
        winner[i] = !(winner[i - 1] && winner[i - 3])
    }
    println(if (winner[n]) "SK" else "CY")
}

 

풀이

---

이전에 풀었을 땐, 그냥 상근이와 창영이가 번갈아서 이기는 걸로 문제를 풀었었다.

하지만 원래라면 dp로 풀어야 하는 문제기 때문에 dp에 대한 감각도 되찾을겸 dp로 해결해 보았다.

 

돌은 1개 또는 3개를 가져갈 수 있음

이렇게 되면 처음 시작하는 사람이 1개를 가져가는 경우, 3개를 가져가는 경우로 나눠볼 수 있다.

 

돌 6개로 게임하는 경우로 예를 들어보자

처음 시작하는 사람이 1개를 가져가는 경우, 남은 돌은 5개

이때 남은 돌을 가지고 다시 게임을 시작

 

상근이가 이기는 경우를 true라고 두자.

만약 dp[i-1], dp[i-3]을 확인했을 때, 창영이가 승리하는 경우가 있다면 i개의 돌이 있을 때 게임은 상근이가 이긴다.

왜 그런지 설명해보자면, dp[i-1]또는 dp[i-3]은 상근이가 마지막에 돌을 가져갈 수 있는 상태이기 때문이다.

(i 번째 돌까지는 아직 돌이 1개 또는 3개가 남았기 때문이다)

 

dp[i-1], dp[i-3]이 모두 상근이가 이기는 경우라면, 창영이가 승리할 수 밖에 없게 된다.