[C++][백준 9655] 돌 게임

[문제]

9655번: 돌 게임 (acmicpc.net)

9655번: 돌 게임

---

[문제 풀이]

게임 이론을 활용한 문제이다.

상근이와 창영이가 각자 돌을 가져가는데 1개나 3개만을 이용해서 가져간다는 것에 주의하자.

 

돌이 처음에 5개가 있을 때 무조건 이길 수 있는 사람이 누구인지 파악해보자.

만약 상근이가 1개를 가자겨면 남은 돌은 4개가 될 테고 이제 창영이가 1개를 가져가든 3개를 자겨가든 남은 돌이 3개 이하가 되므로 무조건 상근이가 이긴다.

 

반대로 돌이 6개일 경우에 무조건 이길 수 있는 사람을 파악해보자.

상근이가 3개를 자겨간다면 다음에 창영이가 3개를 가져가고 상근이가 1개를 가져가면 창영이는 1개씩만을 가져가다가 돌의 개수가 3개 이하가 될 떄를 기다리면 무조건 이긴다.

 

즉, 처음에 시작한 사람은 홀수일 때 무조건 이기고 짝수일 때 무조건 지도록 설정이 되어 있다.

---

[코드]

#include <iostream>

using namespace std;

bool solve(int n){
    if(n % 2 == 0){
        return 1;
    }
    return 0;
}

int main(){
    int n;
    cin>>n;
    (solve(n) > 0) ? cout<< "CY" : cout<< "SK";
    return 0;
}