[BOJ] 27172 - 수 나누기 게임

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

BOJ - 수 나누기 게임

문제 유형: 수학, 정수론

문제 난이도: Gold IV

시간 제한: 1초

메모리 제한: 1024MB

 

문제

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

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

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

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

 

입력

첫 번째 줄에 플레이어의 수 N이 주어집니다. (1 <= N <=10만)

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

 

출력

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

 

풀이

입력 크기를 보면 알겠지만, 당연히 브루트 포스를 하면 TLE가 나온다.

대신, 문제를 더 간결하게 할 필요가 있다.

그 수가 존재하는지에 대한 배열 exists를 만들고, 그 수가 공격당한 횟수 attacked배열을 만든다.

 

플레이어들의 카드 정보를 받아서 배열에 저장해준다. 그러면서, exists에 존재여부를 추가해준다.

 

각 플레이어의 카드별로, 에라토스테네스의 체처럼 그 수의 2배부터 해서 최대 수 상한까지의 모든 배수에 공격표시를 한다.

만약 exists에 존재한다면, 공격이 적중했으므로 점수를 담는 scores배열에 1씩 점수를 누적해준다.

 

최종적으로 득점인 scores[i]에 실점인 attacked[i]를 빼서 각각 출력해주면 된다.

 

while문이 매우 크게 돌 것 같지만, arr[i]가 2인 경우 50만, 3인 경우 33만, .... 점점 급격히 줄어들고, 

100만(1 + 1/2 + 1/3 + ....) = 즉, 시간이 O(n^2)에서 최대 10^10인경우보다는 빠르다!

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int attacked[1000001];
bool exists[1000001];

int n;
int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> n;
  vector<int> arr(n);
  vector<int> wins(n, 0);
  for (int i = 0; i < n; ++i) {
    cin >> arr[i];
    exists[arr[i]] = true;
  }

  for (int i = 0; i < n; ++i) {
    int k = arr[i] * 2;
    while (k <= 1000000) {
      attacked[k]++;
      if (exists[k])
        wins[i]++;
      k += arr[i];
    }
  }

  for (int i = 0; i < n; ++i) {
    cout << wins[i] - attacked[arr[i]] << " ";
  }
  cout << "\n";

  return 0;
}