백준 12107 (약수 지우기 게임 1) c++

문제

12107번: 약수 지우기 게임 1

n이 주어지면 칠판에 1부터 n까지의 자연수를 쓰고 A와 B가 돌아가면서 칠판에 적혀진 자연수를 포함한 약수를 지우는

게임 입니다. 마지막 숫자를 지우는 사람이 지게 됩니다. 선공은 A부터 합니다.

 

1은 모든수의 약수입니다. 따라서 1은 항상 지워집니다. 

만약 내가 이기는 판이면 그대로 게임을 진행하고 

지는 판이면 맨 처음에 1 한개만 지웠다고 가정하고 상대판에게 턴을 넘기면 됩니다.

예를 들어 주어진 숫자가 5이면

1 2 3 4 5 

먼저 A가 4(1, 2, 4)를 지우게 되면 

3 5

다음 B가 3과 5 둘중 아무거나 지워도 결국 A가 지는 판이 됩니다.

그래서 다시 처음으로 돌아가 1 2 3 4 5 중에서 A가 1을 지웠다고 가정하면

2 3 4 5 가 남게 되고 B는 2와 4를 지워 

3 5 가 남게 되고 A가 3과 5 둘중에 한개를 지우면 B가 지는 판이 됩니다.

따라서 주어진 자연수가 1만 아니면 선공이 무조건 이기게 됩니다.

실제로 이기는 최적해를 몰라도 누가 이기는 지를 알 수 있다는 점에서 좋은 문제입니다.

---

전체 코드 입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int n;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n;
    if (n==1)cout << "B";
    else cout << "A";
    
    return 0;
}