[백준/BOJ] 9657번: 돌 게임 3

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

9657번: 돌 게임 3

문제

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

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

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

입력

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

출력

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

해설

상근이가 게임을 우선적으로 시작한다.

돌이 1개가 있다면 상근이가 무조건 이긴다.

돌이 2개일 때 한번에 2개의 돌을 가져갈 순 없으므로 상근이는 무조건 진다.

돌이 3, 4, 5개일 때 상근이는 무조건 이긴다.

 

이제 규칙을 찾아보자.

6개의 돌이 있을 때 dp[6-1], dp[6-3], dp[6-4] 중 상근이가 지는 경우(0)가 있다면 

반대로 상근이가 무조건 이기게 된다.

 

이유는 상근이가 무조건 지는 경우는 상근이가 먼저 시작한 경우인데

dp[6-4]를 보면 상근이는 이미 4개의 돌을 가져갔다.

돌이 2개가 남고 창영이가 먼저 시작한 경우와 같아지게 된다.

 

이와 같이 dp를 통해 1개, 3개, 4개의 돌을 가져갔을 때 0인 경우가 있다면 상근이는 무조건 이기게 된다.

소스 코드

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val dp = IntArray(1001) { 0 }
    dp[1] = 1
    dp[2] = 0
    dp[3] = 1
    dp[4] = 1
    dp[5] = 1
    for(i in 6 .. n) {
        if(dp[i-1] == 0 || dp[i-3] == 0 || dp[i-4] == 0) dp[i] = 1
    }
    if(dp[n] == 1) println("SK")
    else println("CY")
}