[백준 12107 - c++] 약수 지우기 게임 1

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

12107번: 약수 지우기 게임 1

 

아 이런 아이디어 문제 너무 싫다. 이런 거를 어떻게 생각해내는지 모르겠다.

이 문제를 풀 때 가장 중요한 것은 1 은 모든 수의 약수라는 것이다. 풀이를 해보면

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 이 있다 하면 (16이든 뭐든 상관없다).

여기서 1을 잠깐 빼고 생각해보자.

2~16 으로 게임을 할 때 만약 먼저 시작하는 사람이 진다고 가정하면

실제 게임인 1~16 에서는 먼저 시작하는 사람이 처음에 1 을 고르면 2~16이 남고 턴이 상대방에게 넘어가므로 먼저 시작하는 사람이 반드시 이긴다!

또 2~16 으로 게임을 할 때 만약 먼저 시작하는 사람이 이긴다고 하면 1~16 으로 해도 이긴다! 왜나면 2~16 사이의 아무 숫자나 먼저 고르면 1도 같이 지워지면서 시작하기 때문에 2~16이나 1~16이나 똑같다! 

 

이런 이유 때문에 n 이 1 인 경우를 제외하고는 무조건 먼저 시작하는 사람이 이긴다!

 

코드는 간단하다.

#include <iostream>
#include <cstring>
#include <string.h>
#include <string>
#include <cmath>
#include <vector>
#include <numbers>
#include <math.h>
#include <algorithm>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <tuple>
#include <utility>
#include <typeinfo>
#include <iomanip>
#include <set>
#include <map>

using namespace std;

int main(void) {

	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	if (n == 1) cout << 'B';
	else cout << 'A';
	
}