기본적인 게임과 특수한 게임에서의 게임이론을 알아보자.

쉬운 브론즈 문제부터 보자. 이 글을 읽는 당신도 바로 풀 수 있다.

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

게임이론은 아주 작은 상황에서부터 차근차근 머릿속으로 시뮬레이션을 하면서 규칙을 찾으면 쉽게 풀 수 있다. 그렇게 하면 많이 쉬우니 어렵게 생각해 보자.

서로의 간격이 적당히 먼, 건덕이가 왼쪽, 건구스가 오른쪽에 있는 상황이다. 건덕이가 왼쪽으로 도망친다면 건구스도 똑같이 왼쪽으로 갈 수 있다. 즉, 도망쳐봤자 따라잡히므로 도망치는 것은 무의미하다. 덮어두고 도망친다고 모든 일이 해결되지는 않는다. 살다 보면 시간이 해결해주지 않는 일도 존재한다.

그래서 건덕이가 오른쪽으로 간다면 건구스가 왼쪽으로도, 오른쪽으로도 갈 수 있다. 근데 도망치는건 무의미하다. 만약 건구스가 왼쪽으로 가서 서로의 거리가 2만큼 가까워졌다고 하자. 또다시 건덕이의 턴이다. 한 가지 사실을 알 수 있다.

N일 때의 승패가 N-2일 때의 승패와 같다.

N이 2이면 건덕이와 건구스가 바로 붙어 있는 상태니까 공격할 수 있어서 선공인 건덕이가 이긴다. 즉, N이 짝수면 건덕이가 이긴다. 홀수면 건구스가 이긴다.

게임 이론은 이런 식이다. 재미있지 않은가? 계속 해 보자. https://www.acmicpc.net/problem/20004

1부터 N까지 부를 수 있는 베스킨라빈스 게임이다. 1부터 3까지 부를 수 있는 원래 문제를 생각해 보자.

선공이 1, 2를 불렀을 때, 후공이 무슨 수를 불러도 선공이 6을 부를 수 있다. 마찬가지로 10도 부를 수 있다. 이어나가면 14, 18, …, 30을 선공이 부를 수 있으므로, 후공은 31을 불러야 한다.

정리하면, 후공이 숫자를 i(1,2,3)개 부르면 선공은 4-i(3,2,1)개를 항상 부를 수 있다. 선공이 30을 부르면 이기므로, 선공이 30-4-4…-4를 계속 해서 나오는 최소 양수인(30%4) 2를 부르면 이긴다.

N에 대해서는, 선공이 30%(N+1)을 부르면 이긴다. 그런데 이 30%(N+1)이 1, 2, 3, …, N이 아닌 0이면, 1에서 0으로 갈 수는 없으므로 선공이 못 이긴다. 그니까 N==2이면 선공이 진다. 코드는 다음과 같다.

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    int a;cin>>a;
    for(int n=1;n<=a;n++){
        if(30%(n+1)==0){
        cout<<n<<'\\n';
        }
    }

    return 0;
}