문제 링크 : https://www.acmicpc.net/problem/12107

약수 지우기 게임 1

난이도 : 골드 III

문제

A와 B가 약수 지우기 게임을 한다. 약수 지우기 게임은 두 사람이 즐기는 게임이다.

칠판에 1부터 N까지의 자연수가 적혀 있다. 각 사람은 자신의 턴에 칠판에 적힌 자연수 하나를 지우고, 그 자연수의 약수 중 칠판에 남아 있는 수들을 모두 지운다. 예를 들어, 칠판에 2,3,4,5,6이 적혀 있을 때, 6을 지우면, 그 약수인 2와 3 역시 지워야 한다. 자신의 턴에 숫자를 지우지 않을 수는 없다. 마지막 숫자를 지우는 사람이 지게 된다.

A와 B가 최적의 방법으로 게임을 할 때, 이기는 사람을 출력한다. 게임은 A가 먼저 시작한다.

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 A가 이기는 경우 A, B가 이기는 경우 B를 출력한다.

예제 입력 1

4

예제 출력 1

A

힌트

N=4인 경우, A는 처음에 4,2,1을 지운다. 칠판에 남은 수는 3으로, B는 3을 지울 수밖에 없어 패배한다.

문제 풀이

' 1을 제외한 수 ' 를 뽑는 경우의 수를 따져 보면,

2 -> A로 끝나게 된다.
3 -> B로 끝나게 된다. (A가 2 또는 3을 선택한다.)
4 -> B로 끝나게 된다. (A가 2를 선택한다.)
5 -> B로 끝나게 된다. (A가 2를 선택한다.)
6 -> A로 끝나게 된다.
...

• B로 끝나게 되는 경우
  -> A가 선택한 수를 고르면 이길 수 있다.
• A로 끝나게 되는 경우
  -> 1을 선택하여 끝나게 되는 사람을 바꾸면 이길 수 있다.

따라서, N이 1인 경우에만 B가 승리하게 되고, 다른 경우에는 A가 승리하게 된다.

// 정답 코드

#include <iostream>

using namespace std;

int main()
{
    int a;
    cin >> a;
    if(a==1) cout << "B";
    else cout << "A";
}

/*
화살표가 홀수개이면 A가 승리한다.
화살표가 짝수(0포함)개이면 B가 승리한다.

B 1
A 1 2 (12->2)
A 1 2 3 (123->3 or 123->2)
A 1 2 3 4 (1234->3)
A 1 2 3 4 5 (12345->345->45->5)
A 1 2 3 4 5 6 (123456->23456-> (모든 경우의 수에서 A가 승리한다. 화살표가 3개 또는 5개))
...
*/

숫자 '1'이 가진 중요성을 빠르게 찾은거 같아 어렵지 않게 해결 한 문제인 것 같다.