[백준 파이썬] 27172번 수 나누기 게임 (골드 4)

27172번 수 나누기 게임 (골드 4)

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

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

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

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

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

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

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

4. 제한
 - 2 <= N <= 100,000 
- 모든 1 <= i <= N에 대해 1 <= x_i <= 1,000,000입니다.
- 모든 1 <= i < j <= N에 대해 x_i != x_j입니다. 즉, 어떤 수도 x에서 두 번 이상 등장하지 않습니다.

5. 문제 풀이
숫자가 커서 불안하긴 한데... 일단 브루트 포스로 풀어봤다.

>>코드1. 시간초과

"""
27172번 수 나누기 게임
input : 
    n 플레이어의 수
    deck 각 플레이어이 카드 덱
output :
    score 각 플레이어의 점수
"""
n = int(input())
player = list(map(int, input().split()))
score = [0] * n

for i in range(n):
    for j in range(n):
        if i != j:
            iwin = player[i] % player[j]
            ilose = player[j] % player[i] 
            if not ilose  and  iwin:
                score[i] += 1
            elif not iwin and ilose:
                score[i] -= 1

print(*score)

역시나. 시간초과가 나온다.
활용해볼만한 방식은 바로 에라토스테네스의 체이다.

<에라토스테네스의 체 : 소수 찾기>
- 1부터 시작하여, 각각의 소수의 배수들을 제거해 나가는 방식으로 소수를 찾는 방식
- 여기서 차용할 것은, 작은 수부터 시작해서, 각각의 수의 배수를 제거 해나가는 것이다.

우리는 반대로 1 ~ MAX(deck) 에서 deck에 있는 수의 배수를 
앞부터 감점해나가는 방식으로 점수를 계산할 것이다.

그러면, 이중 for 문을 사용하는것인가? >> 맞다.
다만, 사전 처리가 중요하다. 각각의 반복에서 해당 수가 deck에 존재하는 지를 

in으로 검사하다가는 시간복잡도가 O(n) 이 들어 오래 걸린다.
따라서 그냥 exist 리스트에 deck에서 숫자 존재여부를 0/1로 저장해놓는다.
그리고 그냥 해당 인덱스 수가 1인지, 0인지 확인함으로서 존재를 확인한다.

그리고, 배수 또한 작은 수부터 확인해야하는데,
정렬을 시행하는 순간. 시간이 많이 들기 때문에,
동일하게 인덱스가 각각의 수를 가리키는 score 리스트를 만들어 점수를 계산한다.

메모리와 실행시간의 등가교환이다..

>>코드2. 정답입니다.

"""
27172번 수 나누기 게임
input : 
    n 플레이어의 수
    deck 각 플레이어이 카드 덱
output :
    score 각 플레이어의 점수
에라토스테네스의 체 : 소수 골라내기 
1 부터 소수인 수의 배수들을 제거해나가는 방식

소수 : 소수의 배수만큼 점수 획득
소수의 배수 : 약수로 가진 배수만큼 점수 -1
"""
import sys
input = sys.stdin.readline

n = int(input())
player = list(map(int, input().split()))
m = max(player)
exist = [0] * (m+1)
score = [0] * (m+1)

# 카드 존재 표시
for x in player:
    exist[x] = 1

# 배수관계 처리
for x in player:
    for y in range(x*2, m+1, x):
        if exist[y]:
            score[x] += 1
            score[y] -= 1

for x in player:
    print(score[x], end = " ")

6. 문제 링크
https://www.acmicpc.net/problem/27172