[백준] 27172 - 수 나누기 게임 (G5)

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

27172번: 수 나누기 게임

 

에라토스테네스의 체를 구하는 과정을 응용하여 푸는 문제이다.

수가 10만개 이므로, 임의 두 수의 쌍을 모두 구해서 대결을 시키는 것은 시간내에 풀 수 없다.

 

1. 미리 1부터 100만까지 모든 수에 대한 점수를 저장할 리스트를 만들어 두고, None으로 초기화를 시켜둔다.

(점수가 음수가 될 수 있기 때문이다)

 

2. 플레이어가 가진 수로 주어진 모든 수에 대해 점수를 0으로 설정한다.

 

3. 각 플레이어의 수에 대해 에라토스테네스의 체를 구하듯, 그 수의 모든 배수에 대해 None이 아니라면(그 수를 가진 플레이어가 존재한다면), 자신의 수가 이겼으니 +1, 상대 수에 대해 -1 을 설정한다.

 

점수 결과를 출력한다.

 

l = [None for _ in range(1000001)]
n = int(input())
nums = list(map(int, input().split()))
for num in nums:
    l[num] = 0

for num in nums:
    for j in range(num, 1000001, num):
        if l[j] is not None:
            l[j] -= 1
            l[num] += 1

print(*[l[num] for num in nums])

 

풀이는 간단한데, 에라토스테네스의 체로 풀어야겠다는 생각을 하기가 쉽지는 않을 수도 있겠다는 생각이 든다.

알고리즘 분류를 봐도 조금 고민을 하게 했던 문제.

풀고나니까 에라토스테네스의 체 구현을 응용하는 아이디어가 너무 돋보여서 신박했다.

Solved.ac 클래스 문제에 있는 이유가 있는 것 같다.