백준 9655 돌 게임 Kotlin (dp,수학,게임 이론)

문제 출처 : https://www.acmicpc.net/problem/9655

9655번: 돌 게임

문제

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)

출력

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

알고리즘 분류

• 수학
• 다이나믹 프로그래밍
• 게임 이론

풀이

글 제목에 알고리즘 분류를 모두 적은 이유는, 본인은 수학으로 풀었지만,  dp, 게임 이론 모두 공부하기 좋은 문제이기 때문이다. 

수학을 이용한 풀이는 그냥 몇 개 계산해보면 짝수면 창영이가 이기고 홀수면 상근이가 이긴다.

어느 분의 dp 풀이를 보고 dp로 풀어보려 했으나 이해가 안 돼서 포기,

게임 이론은 스프라그-그런디 정리를 이용해 풀 수 있으나 내용이 어려우니 시간 날 때 도전해봐야겠다.

 

 

코드

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    //홀SK 짝CY
    var n = Integer.parseInt(br.readLine())
    if(n and 1 ==1){
        write("SK")
    }
    else{
        write("CY")
    }

    close()
}