백준/코드포스 게임이론 유형 쉽게 푸는 법

9661번: 돌 게임 7

얼마전에 코드포스를 계속 망쳐서 연속으로 점수를 많이 떨궜다. 해당 라운드들을 망한 원인은 공통적으로 내가 게임이론을 말아먹었다는 것이다. C번에서 계속 게임이론이 나왔는데 엄청 많이 틀리거나 or 아예 못풀거나 해서 퍼포가 계속 낮게 떴는데 다음에 또 게임이론이 나오면 레이팅 다시 망하는 건 시간문제라는 생각이 들었다(실제로 자주 나오기도 하고). 그래서 다시는 이런일이 없도록 백준에서 게임이론 태그가 붙은 문제들을 무지성으로 풀어보았고, 나름대로 나만의 방식이 생긴것 같다. 고수분들은 이런 과정 없어도 딱딱 답안을 내시겠지만 나는 아니라서...

 

백준에서 두 플레이어가 턴을 번갈아 가며 하는 문제들은 아래의 세단계를 거치면 대부분 풀 수 있는 것 같다.

 

1) 선공이 어떤 행동을 하더라도 항상 지는 경우를 어떻게 표현할지 생각하기.

2) 1)번 내용을 DP로 구현하여 여러 케이스의 답을 출력하기.

3) 규칙성 찾기.

 

이 방식을 활용하여 위의 백준 9661 : 돌 게임 7 문제를 풀어보도록 하겠다.

주어진 문제를 보면 돌 N개(1 <= N <= 1,000,000,000,000)개를 상근이부터 시작하여 차례대로 4의 아무 제곱수만큼 돌을 가져가고 더이상 가져갈 방법이 없는 사람이 게임을 진다고 한다. 그럼 위의 세 단계를 활용하여 문제를 풀어보겠다.

 

1. 선공이 어떤 행동을 하더라도 항상 지는 경우를 어떻게 표현할지 생각하기

풀이 전에 하나의 규칙이 있는데, 게임 이론 문제에서 DP(N)은 항상 "N의 상태로 턴을 시작하는 사람이(선공이) 이기는 방법이 있다/없다"를 의미한다. 이를 명심하고 1번 단계를 풀어야 한다.

 

현재 돌이 N개 있다고 가정하자. 이때 선공이 어떤 행동을 하더라도 항상 진다는 것이 무슨 의미일까? 말 그대로 x가 무엇이든 간에 N개의 돌 중 4^x개 돌을 가져가고 후공에게 턴을 넘기면 무조건 진다는 것이다. 후공의 입장에서 바꿔말하면 모든 x에 대하여 턴이 넘어와가지고 N - 4^x개의 돌이 있는 상태에서 선공의 입장이 되면 이긴다는 것과 동일하다. 만일 단 하나라도 후공을 패배시키는 x가 있다면 선공이 최적으로 플레이하면 이길 수 있게된다.

즉, DP(N)은 만일 DP(N - 1), DP(N - 4), DP(N - 16), ...이 모두 true라면 false이고, (이번 턴에 뭘 하든 후공이 항상 승리)

DP(N - 1), DP(N - 4), DP(N - 16), ... 중 단 하나라도 false가 있다면 true 이다. (이번 턴에 후공을 패배시키는 방법이 존재)

=> DP(N) = ~(DP(N-1) & DP(N-4) & DP(N-16) & DP(64) & ... )

 

이는 일단 겪어본 바로는 대부분의 게임이론 문제에서 거의 적용 가능한 사고 흐름인 것 같다. 다이아5 티어인 돌 게임 8 문제에도 통했으니까..?

1) 선공이 무조건 지는 경우 (DP(N) = false로 정해지는 경우)

=>  N개의 상황에서 선공이 어떤 행동을 하더라도 턴을 넘겨서 후공이 선공 입장이 되면 항상 이기는 경우

= 이번 턴에 뭘 하든 후공이 항상 승리

= DP(N-1), DP(N-2), DP(N-3), ... 이 모두 true

2) 선공이 이기는 방법이 있는 경우 (DP(N) = true로 정해지는 경우)

=> N개의 상황에서 단 하나라도 턴을 넘겨서 후공이 선공 입장이 되었을 때 지게 만드는 방법이 있는 경우

= 이번 턴에 후공을 패배시키는 방법이 존재

= DP(N-1), DP(N-2), DP(N-3), ... 중 하나라도 false

 

그럼 이걸 이제 코드로 옮겨볼 차례이다.

 

2. 1번 내용을 DP로 구현하여 여러 케이스의 답을 출력하기

int memo[1001];

 

int dp(int n) {
    if (memo[n] != 0) return memo[n];
    int x = 1;
    while (x <= n) {
        if (x == n) return memo[n] = 1;       //n 자체가 4의 제곱수면 바로 이긴다.
        if (dp(n - x) == -1) return memo[n] = 1; // 단 하나라도 턴을 넘겼을 때 상대가 지는 경우가 존재하면 선공이 이긴다.
        x *= 4;
    }
    return memo[n] = -1;     //돌을 얼마를 가져가더라도 항상 상대가 이긴다 == 선공이 진다.
}

 

그대로 구현하는 것은 어렵지 않다. 그럼 이걸 출력해보고 규칙을 찾을 차례이다.

 

3. 규칙성 찾기

아주 뚜렷한 규칙성이 보인다! 5를 주기로 선공의 승, 패, 승, 승, 패가 반복되고 있다. 그러면 이제 답안을 작성하는 것은 어렵지 않다. N % 5가 2거나 0이면 후공인 창영이의 승이고, 그렇지 않다면 선공인 상근이의 승이다.

 

결국 최종 정답 코드는 다음과 같이 된다. N의 범위를 잘 보고 long long을 쓰는 것도 잊으면 안된다!

 

백준 9661 : 돌 게임 7 - 정답 코드

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    cout << (n % 5 == 2 || n % 5 == 0 ? "CY" : "SK");
    return 0;
}