[Python] 27172번 수 나누기 게임

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

27172번: 수 나누기 게임

---

 

23/12/05

 

 

기존 에라토스테네스의 체 알고리즘을 응용한 문제로, 정확히 말하면 체의 원리를 이용한 문제여서 조금 신선하다고 할 수 있다.

 

클래스 5에도 있는 교육적인 문제이니, 안보고 해결하면 좋을 문제인 것 같다.

 

---

 

문제 접근 방식:

 

 

어떤 수가 다른 수의 약수가 되면, 그 수는 점수를 얻는 방식이다.

 

예를 들어 $3$과 $12$가 서로 게임을 한다고하면 $3$은 1점을 얻고 $12$는 1점을 잃는다.

 

에라토스테네스의 체의 원리를 생각해보면, 소수가 아님을 찾아내기 위해 특정 소수의 배수들을 체에서 배제하는 과정이 존재한다.

 

이를 생각하여 체를 구성한다면, 우리는 게임의 카드들 중 가장 큰 숫자만큼의 크기를 가진 체를 구성해야 함을 알 수 있다.

 

즉, 게임의 카드들 중 가장 큰 카드의 숫자를 $\mathrm{max}(card) = M$이라고 한다면, $M$의 크기를 가진 체를 구성한다고 하자.

 

이제 게임의 카드들 하나 하나마다, 그 배수들에 대해 게임을 진행해 주면 된다. 이때, 배수가 게임 카드들에 존재할 때에만 체에 결과를 저장하면 된다.

 

나의 경우, 배수가 게임 카드들에 존재하는지에 대한 여부는 집합으로 확인해주었다.

 

물론 bool 배열을 사용하여 구현할 수도 있을 것이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 27172번 수 나누기 게임
# 에테체
import sys
input = sys.stdin.readline

N = int(input())
x = list(map(int, input().rstrip().split()))
S = set(x)
M = max(x)
sieve = [0 for _ in range(M+1)]
for i in x:
    if i == M: continue
    for j in range(2*i, M+1, i):
        if j in S:
            sieve[i] += 1
            sieve[j] -= 1
for i in x:
    print(sieve[i], end = ' ')