[백준 9655] 돌 게임 | KOTLIN

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

문제 설명

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

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

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

입력

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

출력

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

예제 입력 1

5

예제 출력 1

SK

분류

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

---

풀이

참고 블로그: https://beginnerdeveloper-lit.tistory.com/83

n=1 부터 n=10까지 해보면서 다이나믹 프로그래밍으로 풀 생각을 못했다..! 블로그 풀이보고 DP 로 해결..!

코드

val dp = Array(1002){0}

fun min(a: Int, b: Int) = if (a > b) b else a

fun calcDP(n: Int) : Int {
	dp[1] = 1
	dp[2] = 2
	dp[3] = 1

	for (i in 4..n) {
		dp[i] = min( dp[i-1] + 1, dp[i-3] + 1)
	   // println("dp[$i]: ${dp[i]}")
	}
	return dp[n]
}

fun main(args: Array<String>) {
    val n = readLine()?.toInt()

	val res = calcDP(n!!)
	// println("res: $res")
	
	println(if (res % 2 == 0) "CY" else "SK" )
}