백준 27172-수 나누기 게임(python) (에라토스테네스 아이디어 응용)

정수론, 수학문제에 해당하는 수 나누기 게임

에라토스테네스의 체의 아이디어를 응용하면 풀 수 있었다.

import sys
input = sys.stdin.readline
print = sys.stdout.write
n = int(input().rstrip())
num = list(map(int, input().rstrip().split()))
m = max(num)
point = [0 for i in range(m+1)]
visit = [0 for i in range(m+1)]
for i in num:
    visit[i] = 1
for i in num:
    j = i
    k = 2
    while j*k <= m:
        point[j*k] -= 1
        if visit[j*k] == 1:
            point[i] += 1
        k+=1
for i in num:
    print("%d "%point[i])

코드는 간단한 편이지만, 아이디어적인 문제로써 매우 의미가 있는 문제이다.

일단 문제의 규칙을 보자

1. 모든 사람은 카드에 수를 부여받는다

2. 모든 사람은 각 사람과 대결을 하며, 그 대결은 자신의 카드의 수로 상대의 수를 나누어떨어지게 할 수 있는가?로 결정된다.

3. 나눌 수 있다면 1점을 얻고 만약 상대가 자신의 카드를 나눈다면 1점을 잃는다.

 

직관적인 아이디어: 브루트 포스?

이 경우 O(n^2) = 10^10정도라서 시간제한을 넘긴다.

 

배열을 만들고, 미리 나누어지는 수는 1점을 제거해주면 된다.

만약 미리 나누어지는 수가 상대의 패에 있는 수라면 현재 탐색하고 있는 자신의 점수를 1점 늘린다.

 

이는 에라토스테네스의 체 알고리즘과 매우 유사하다.

 

코딩초보 무끝을 귀여워해주세요! ><