[백준/27172] 수 나누기 게임 (Python)

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

27172번: 수 나누기 게임

 

Difficulty : Gold 5

 

Status : Solved

 

Time : 00:11:39

 

---

 

문제 설명

 

 

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

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

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

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

 

 

입력 및 출력

 

입력

 

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

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

 

출력

 

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

 

입력 예시

 

3
3 4 12

 

출력 예시

 

1 1 -2

 

 

---

 

풀이

 

단순히 브루트포스로 풀게 되면, O(N^2)의 끔찍한 시간복잡도를 얻게 된다. 최대 N = 10^5이므로 당연히 시간 초과이다.

 

하지만 숫자가 중복되지 않는다는 점, 숫자의 범위는 10^6까지의 양의 정수로 훨씬 탐색 범위가 줄어든다. 즉 '에라토스테네스의 체' 기법을 응용하여 쉽게 계산해볼 수 있다. 1부터 10^6까지의 숫자 중, 보드게임 참가자가 지닌 숫자가 있으면 그 배수를 탐색하여 일치하는 참가자들끼리 점수 계산을 시행한다. (배수 관계이면 반드시 나머지가 0이 되기 때문이다)

 

이 연산의 최악의 경우, 1 ~ 100000까지의 참가자가 존재하는 경우가 될 수 있겠다. 이 때는 연산의 가짓수가 (10^6 // 1 + 10^6 // 2 .... ) 꼴이 되며, 이는 10^6에 (1 + 1/2 + ... + 1/X) 꼴의 조화수열 합을 곱한 것과 동일하다. 따라서 전체 시간복잡도는 O(NlogX)에 가깝다.

 

풀이 코드

MAX = 1000001
N = int(input())

nums = [-1]*MAX
num_list = list(map(int, input().split()))

for idx, num in enumerate(num_list) :
  nums[num] = idx

score_list = [0]*N

for i in range(MAX) :
  if nums[i] > -1 :
    for j in range(i*2, MAX, i) :
      if nums[j] > -1 :
        score_list[nums[i]] += 1
        score_list[nums[j]] -= 1

print(*score_list)

풀이 완료!