[C++] 백준 27172 수 나누기 게임

https://www.acmicpc.net/problem/27172
제목 : 수 나누기 게임
난이도 : Gold V

풀이

플레이어 각자는 수를 하나씩 갖고 있다. 플레이어 끼리 수를 나누어 나머지가 0이면 낮은 수를 가진 플레이어가 이긴다.
예를 들어, A 가 3을, B가 6을 들고 있다고 가정해본다.
6을 3으로 나누면 나머지가 0 이지만 3을 6으로 나누면 나머지가 3이다. 그렇게 되면 A플레이어가 1점을 먹고, B플레이어가 -1점을 먹는다.

우리는 이걸 에라토스테네스의 채로 응용할 수 있다.
에라토스테네스의 채는 2부터 N 까지의 수의 배수를 탐색하며 나누어 떨어지면 false가 되는 소수 판별법이다.

우리는 한 플레이어의 수를 가지고 배수를 탐색하여 배수중에 다른 플레이어의 수가 있는지 찾아보면 된다.
만약 있으면 기존 플레이어의 점수를 1점 올리고 그 반대 플레이어는 점수를 1점을 깎는다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N, num;
    cin >> N;
    vector<int> nums(1000001, 0);
    vector<int> check(1000001, 0);
    vector<int> player;
    for (int i = 0; i < N; i++) {
        cin >> num;
        player.push_back(num);
        check[num] = 1;
    }
	
    for (int i : player) { // 플레이어가 갖고 있는 숫자로 탐색
        for (int j = 2 * i; j <= 1000000; j += i) {
            if (check[j] == 1) { 
            // 플레이어가 갖고 있는 숫자의 배수를 다른 플레이어가 갖고 있으면
            // 기존 플레이어의 점수를 올리고, 배수를 갖고있는 플레이어의 점수를 내린다.
                nums[i]++;
                nums[j]--;
            }
        }
    }

    for (int i : player) {
        cout << nums[i] << " ";
    }
}