# [Gold III] 약수 지우기 게임 1 [문제 링크](https://www.acmicpc.net/problem/12107) ## 문제 설명 <p>A와 B가 약수 지우기 게임을 한다. 약수 지우기 게임은 두 사람이 즐기는 게임이다.</p> <p>칠판에 1부터 N까지의 자연수가 적혀 있다. 각 사람은 자신의 턴에 칠판에 적힌 자연수 하나를 지우고, 그 자연수의 약수 중 칠판에 남아 있는 수들을 모두 지운다. 예를 들어, 칠판에 2,3,4,5,6이 적혀 있을 때, 6을 지우면, 그 약수인 2와 3 역시 지워야 한다. 자신의 턴에 숫자를 지우지 않을 수는 없다. 마지막 숫자를 지우는 사람이 지게 된다.</p> <p>A와 B가 최적의 방법으로 게임을 할 때, 이기는 사람을 출력한다. 게임은 A가 먼저 시작한다.</p> ## 입력 <p>첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.</p> ## 출력 <p>첫째 줄에 A가 이기는 경우 A, B가 이기는 경우 B를 출력한다.</p> ## 풀이 #### N이 1일 때는 1을 선택하는 경우밖에 없으니 A가 항상 게임에서 진다. #### N이 1이 아닌 경우, 이길 수 있다면 그대로 이기면 되고, 이길 수 없다면 첫 턴에 1을 선택해서 결과를 스위칭하면 이길 수 있다. 첫 턴에서 1개만 지우는 경우는 1을 선택해 지우는 것이 유일하고 이 경우 필패 - 필승 결과가 스위칭된다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; if(n!=1) cout << 'A'; else cout << 'B'; } ```