백준 12107 약수 지우기 게임 1

작성일 | In |

Problem : 약수 지우기 게임1

유형 : 게임이론

문제 설명

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

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

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

예제 입력

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

1
4

예제 출력

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

1
A

해결 전략

A와 B가 최적의 방법으로 게임을 할 때 를 캐치해야 한다.
자기보다 작은 약수가 없는 수는 1 밖에 없다.
1을 무시하고 다른수만 볼때, A가 항상 지는 경우가 나오는 경우에는 A는 1을 지워버리면 이긴다.

주의할 점

  • 잘 생각해보기…?

풀이

A가 선턴이므로 하나의 경우만 제외하고 항상 이긴다.

  • 단 하나의 경우는 시작하자마자, A가 자멸하는 경우뿐이다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int n;

void solve() {
    cin >> n;
    if (n == 1)cout << "B\n";
    else cout << "A\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    cin.tie(NULL);  cout.tie(NULL);

    solve();

    return 0;
}

피드백

재밌는 문제