백준 22984번: 수 나누기 게임 [Python]

작성일 | In
골드 IV 골드 IV

문제

수 나누기 게임
에라토스테네스의 체 알고리즘의 아이디어를 이용해 $O(\sum_{k=1}^n \frac{N}{x_k})$에 풀 수 있습니다.
$x_k$들은 각기 다르므로 시간복잡도는 $O(10N)$정도가 됩니다.

풀이

에라토스테네스의 체에서 어떤 수의 배수를 거르면서 소수를 찾듯이, 이 문제에서는 어떤 수의 배수와 결투해서 점수를 결정합니다.
어떤 수 $i$에 대해 $N$까지의 $i$의 배수끼리만 결투하면 됩니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = int(input())
players = list(map(int, input().split()))
playerSet = set(players)
maxNum = max(players)
score = [0 for _ in range(maxNum + 1)]

for i in players:
    for j in range(i, maxNum + 1, i):
        if j in playerSet:
            score[i] += 1
            score[j] -= 1

for i in players:
    print(score[i], end=" ")

백준 22984번: 수 나누기 게임 [Python]