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

27172번: 수 나누기 게임

문제 요약

문제

《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다.

《수 나누기 게임》의 규칙은 다음과 같습니다.

• 게임을 시작하기 전 각 플레이어는 $1$부터 $1\,000\,000$ 사이의 수가 적힌 서로 다른 카드를 잘 섞은 뒤 한 장씩 나눠 가집니다.
• 매 턴마다 플레이어는 다른 플레이어와 한 번씩 결투를 합니다.
• 결투는 서로의 카드를 보여주는 방식으로 진행되며, 플레이어의 카드에 적힌 수로 다른 플레이어의 카드에 적힌 수를 나눴을 때, 나머지가 $0$이면 승리합니다. 플레이어의 카드에 적힌 수가 다른 플레이어의 카드에 적힌 수로 나누어 떨어지면 패배합니다. 둘 다 아니라면 무승부입니다.
• 승리한 플레이어는 $1$점을 획득하고, 패배한 플레이어는 $1$점을 잃습니다. 무승부인 경우 점수의 변화가 없습니다.
• 본인을 제외한 다른 모든 플레이어와 정확히 한 번씩 결투를 하고 나면 게임이 종료됩니다. 《수 나누기 게임》의 결과를 가지고 한별이와 내기를 하던 은하는 게임이 종료되기 전에 모든 플레이어의 점수를 미리 알 수 있을지 궁금해졌습니다. 은하를 위해 각 플레이어가 가지고 있는 카드에 적힌 수가 주어졌을 때, 게임이 종료된 후의 모든 플레이어의 점수를 구해주세요.

사용 알고리즘

에라토스테네스의 체

입출력

• 입력: 첫 번째 줄에 플레이어의 수 $N$이 주어집니다. 두 번째 줄에 첫 번째 플레이어부터 $N$번째 플레이어까지 각 플레이어가 가지고 있는 카드에 적힌 정수 $x_{1}$, $\cdots$, $x_{N}$이 공백으로 구분되어 주어집니다.
• 출력: 첫 번째 플레이어부터 $N$번째 플레이어까지 게임이 종료됐을 때의 각 플레이어의 점수를 공백으로 구분하여 출력해주세요. ``` 예제1

입력 3 3 4 12 출력 1 1 -2

## 풀이
그냥 단순히 이중 for문으로 반복하면 시간초과 걸린다.(해봄) 푸는 방법은 에라토스테네스의 체를 활용해서 배열을 크게 만든 후 그 배열에서 숫자가 있는 곳을 표시해서 접근하는데 걸리는 시간을 줄이는 것이다.

## 어려웠던 점
처음에 에라토스테네스를 어떻게 활용해야 되는지 헷갈렸다.

## 배운 점 / 느낀 점
소수 관련은 에라토스테네스가 짱이라는 것을 알게 되었다. 

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<int> card;
bool a[1000009];
int point[1000009];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    card = vector<int>(n);

    for(int i = 0; i < n; i++){
        cin >> card[i];
        a[card[i]] = true;
    }


    for (int i = 0; i < n; i++) {
        int t = card[i];
        for (int j = t*2; j < 1000009; j+=t) {
            if(a[j]){
                point[t] += 1;
                point[j] -= 1;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << point[card[i]] << ' ';
    }

    return 0;
}