[Baekjoon/C++] 27172번 - 수 나누기 게임

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

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

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

《수 나누기 게임》의 결과를 가지고 한별이와 내기를 하던 은하는 게임이 종료되기 전에 모든 플레이어의 점수를 미리 알 수 있을지 궁금해졌습니다. 은하를 위해 각 플레이어가 가지고 있는 카드에 적힌 수가 주어졌을 때, 게임이 종료된 후의 모든 플레이어의 점수를 구해주세요.

 

입력

첫 번째 줄에 플레이어의 수 𝑁이 주어집니다.

두 번째 줄에 첫 번째 플레이어부터 𝑁번째 플레이어까지 각 플레이어가 가지고 있는 카드에 적힌 정수 𝑥, ⋯, 𝑥𝑁이 공백으로 구분되어 주어집니다.

 

출력

첫 번째 플레이어부터 𝑁번째 플레이어까지 게임이 종료됐을 때의 각 플레이어의 점수를 공백으로 구분하여 출력해주세요.

 

제한

•  2≤𝑁≤100000
• 모든 1≤𝑖≤𝑁에 대해 1≤𝑥𝑖≤1000000입니다.
• 모든 1≤𝑖<𝑗≤𝑁에 대해 𝑥𝑖≠𝑥𝑗입니다. 즉, 어떤 수도 𝑥에서 두 번 이상 등장하지 않습니다.

 

---

풀이

#include <iostream>
using namespace std;

int N, mx;
int player[100001];
int card[1000001];
bool check[1000001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    // 입력
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> player[i];

        check[player[i]] = true;
        mx = max(mx, player[i]);
    }

    for (int i = 0; i < N; i++) {
        int nowCard = player[i];

        for (int j = nowCard * 2; j <= mx; j += nowCard) {
            if (check[j]) {
                card[nowCard]++;
                card[j]--;
            }
        }
    }
    
    // 출력
    for (int i = 0; i < N; i++) cout << card[player[i]] << ' ';
    cout << '\n';

    return 0;
}

 

    for (int i = 0; i < N; i++) {
        int nowCard = player[i];

        for (int j = nowCard * 2; j <= mx; j += nowCard) {
            if (check[j]) {
                card[nowCard]++;
                card[j]--;
            }
        }
    }

 각 플레이어의 점수를 계산하는 코드이다. player에 저장된 숫자를 시작점으로 삼고, 그 숫자의 배수에 해당하는 칸이 다른 플레이어가 가지고 있는 카드라면(check[j] == true) now 플레이어에게 점수를 주고 j플레이어의 점수를 줄인다. 이러한 반복은 입력을 받을 때 구한 가장 큰 카드의 숫자보다 j가 커지면 멈추게 된다.