BOJ-9655 돌 게임 Swift

문제

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

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

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

입력

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

출력

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

내가 푼 풀이

- 문제를 이해하기 어려웠는데,, 마지막 돌을 가져간사람이 이기게된다.

- 돌이 2개남았을때, 3개를 가져가서 마지막돌을 가져가는것이 아니라, 3개미만으로 남았을땐 1개씩밖에 못가져간다.

- 이렇게 마지막돌을 가져간 사람이 우승하는것이다.

- 돌이 1개있다면, 상근이가 먼저시작하므로 상근이가 1개 가져가면 이기게된다.

- 돌이 2개있다면, 상근이가 1개 가져가고, 창영이가 마지막돌 1개를 가져가므로 창영이가 이기게된다.

- 돌이 3개가 있다면, 상근이가 먼저 3개를 가져가면 마지막돌을 가져가므로 상근이가 이기게된다.

- 이를 점화식으로 만들어보자.

- dp[n] = n개의 돌이 있을때, 진행되는 순서 로 정의하자.

- dp[1] = 1, dp[2] : 총 두차례가 진행되므로 dp[2] = 2, dp[3]: 3개 가져가므로 한차례에 게임이 끝난다 dp[3] = 1

- n % 3 == 0 이라면 dp[n] = n / 3

- n % 3 != 0 이라면 dp[n] = dp[i / 3] + dp[i % 3] 이 된다.

 

이렇게 진행된 순서의 수가 홀수라면, 마지막돌을 가져간 사람은 상근이고, 짝수라면 창영이다.

 

import Foundation

var num = Int(readLine()!)!

var dp = Array(repeating: 0, count: 1001)
dp[1] = 1
dp[2] = 2
dp[3] = 1

// dp
for i in 1...1000 {
    if i % 3 == 0 {
        dp[i] = i / 3
    } else {
        dp[i] = dp[i/3] + dp[i%3]
    }
}

if dp[num] % 2 != 0 {
    print("SK")
} else {
    print("CY")
}