백준(BOJ) 11867 : 박스 나누기 게임

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

11867번: 박스 나누기 게임

 

신나는 게임이론

 

공책에 좀 끄적이다보니 규칙이 보였다.

두 상자중 한 상자라도 2개짜리가 존재한다면 1, 1 로만들 수 있으니 승리할 것이다.

3개짜리의 상자는 1, 2로 밖에 만들 수 없으므로 패배할 수 밖에 없다.

이걸 토대로 규칙을 찾아보도록 하자.

 

4개 -> (1, 3), (2, 2)

2, 2로 나눌 경우 항상 승리하므로 4개짜리 상자는 승리를 가져다준다.

5개 -> (1, 4), (2, 3)

어떻게 나누어도 상대가 승리할 수 밖에없다. 첫번째 경우에는 위에서 구한대로 4개면 승리하므로 패배하고 두번째 경우에는 3이 존재하더라도 상대가 2를 선택하여 분배하면 되기 때문이다.

 

6개 -> (1, 5), (2, 4), (3, 3)

(3, 3)으로 분배할 경우 상대가 패배할 수 밖에 없으므로 승리한다.

 

7개 -> (1, 6), (2, 5), (3, 4)

어떻게 분배해도 패배한다. 각 경우에 6, 2, 4가 존재하기 때문

 

고로 N M 중 하나라도 짝수가 존재한다면 승리할 수 있다는 소리가된다.

아래는 소스코드이다.

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 987654321;


int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false); 

  int N, M;
  cin >> N >> M;


  if(N % 2 == 0 || M % 2 == 0) {
    cout << "A" << endl;
  }
  else {
    cout << "B" << endl;
  }
}