[백준 27172번] 파이썬 - 수 나누기 게임

백준 27172_수 나누기 게임

시간 제한 1초, 메모리 제한 1024MB

# 조건

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

입력

• 첫 번째 줄에 플레이어의 수 N이 주어집니다.
• 두 번째 줄에 첫 번째 플레이어부터 N번째 플레이어까지 각 플레이어가 가지고 있는 카드에 적힌 정수 $x_{1}$, ⋯$\cdots$, $x_{N}$이 공백으로 구분되어 주어집니다.

출력

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

# 제한

•  2 <= N <= 100,000
• 모든 1 <= i <= N에 대하여 1<= $x_{i}$ <= 1,000,000 입니다.
• 모든 1<= i < j <= N에 대해 xi != xj 입니다.
  • 즉, 어떤 수도 x에서 두 번 이상 등장하지 않습니다.

# 접근 방법

• 모든 사람의 대결을 펼친다면 100,000^2 이 되어 시간 초과가 발생한다.
• 따라서, 등장하는 숫자를 dp 배열에 기록해주고 플레이어가 가진 카드를 순회한다.
• 작은 수부터 배수만큼 순회하며 해당 카드를 가진 플레이어가 존재한다면 시작 카드는 + 1, 배수만큼 곱해진 카드는 -1 을 해주면 된다.
  • 이를 위해서 sort가 아닌 sorted()를 이용하여 원본 배열은 유지시켜준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  


N = int(input())  
nums = [*map(int, input().split())]  
a = max(nums)  
dp = [0] * (a+1)  
for i in nums:  
    dp[i] = 1  

result = [0] * (a+1)  

for i in sorted(nums):  
    for j in range(i*2, a+1, i):  
        if dp[j]:  
            result[i] += 1  
            result[j] -= 1  

for k in nums:  
    print(result[k], end=" ")