구슬 게임

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• 처음 문제를 접했을 때, 완전탐색으로 문제를 설계하기가 까다로움
• 따라서 규칙을 살펴보면, 구슬은 1개 ~ 3개 가져갈 수 있으므로, 1 ~ 3개일 때는 철수가 먼저 가져가므로 이길 수 밖에 없음
• 4개의 경우 따져보면, 영희가 이길 수 밖에 없음 5개 6개 7개 일때는 철수가 이길 수 있는 경우가 있음
• 8개의 경우 영희가 이길 수 밖에 없음. 따라서 4로 나누어 떨어지는 경우, 영희가 이기고 아닌 경우는 철수가 이길 가능성이 있는 것을 간단하게 알 수 있지만, 동적계획법을 풀이할 수도 있음
• 철수와 영희가 공평하게 번갈아 가면서 구슬을 최선을 다해 가져가므로, 현재 시점이 철수가 구슬을 가져가는 시점이라고 가정하면, 
• 이전 시점에서 영희가 구슬을 1개 가져갔을 때, 2개 가져갔을 때, 3개 가져갔을 때 모두 승리라면 철수가 이길 가능성은 없고, 한가지 경우라도 패배인 경우가 있다면 철수가 이길 가능성이 있는 것을 알 수 있음
• 두 알고리즘 모두 O(N)으로 문제를 해결할 수 있음

5. 전체 코드

//MARK: - 구슬 게임

//MARK: - Framework
import Foundation

//MARK: - Function
func solution() -> Void {
    //MARK: - Input
    guard let n: Int = Int(readLine() ?? "0") else { return }
    var marbleGames: [Bool] = Array(repeating: false, count: n + 10)
    let baseCondition: Int = 3
    
    //MARK: - Process
    //1. 부분 문제를 정의한다.
    //n개의 구슬이 주어졌을 때, 1개, 2개, 3개씩 가져간다 했을 때, 철수가 이길 수 있는지 구해야 함.
    //T[i] = 철수가 이길 경우가 한개라도 있으면 true, 없으면 false
    
    //2. 점화식을 세운다.
    //각 게임은 철수부터 시작해서 공평하게 한번씩 진행되는 것과, 한 번에 1개 혹은 2개 혹은 3개를 가져갈 수 있다는 점에 유의해서
    //현재 시점에서 이전 결과에 의해 결정이 됨
    //T[i] = 1개 가져갔을 때 결과 && 2개 가져갔을 때 결과 && 3개 가져갔을 때 결과
    //즉, T[i] = T[i - 1] && T[i - 2] && T[i - 3] ? false : true(이전 결과는 영희의 차례 이므로 반대가 되어야 함)
    for i in 1...baseCondition {
        marbleGames[i] = true
    }
    
    for i in stride(from: baseCondition + 1, through: n, by: 1) {
        marbleGames[i] = marbleGames[i - 1] && marbleGames[i - 2] && marbleGames[i - 3] ? false : true
    }
    
    //MARK: - Output
    print(marbleGames[n] ? "YES" : "NO")
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.