ALGORITHM

[알고리즘 스터디 - 1주차 3] 소수 게임

난이도

Gold 4

문제

인하대학교에 다니는 대웅이는 정수론을 정말 좋아한다. 정수론을 광적으로 좋아하는 대웅이는 어느 순간부터 소수를 외우기 시작했고 어떤 수를 말하면 그 수가 소수인지 아닌지 판별할 수 있는 능력을 가지게 되었다. 인하대학교에 소수의 신이 있다는 소문이 퍼지자 인상대학교의 소수 마스터 규성이는 대웅이에게 도전장을 내밀었다.

둘은 누가 더 소수를 사랑하는지 내기를 하기로 하였다.

하지만 누가 더 소수를 사랑하는지에 대한 기준이 없으므로 소수 게임을 이용하기로 하였다.

소수게임의 규칙은 다음과 같다.

두 사람이 번갈아가며 소수를 말한다. 소수가 아닌 수를 부르게 될 경우 상대방은 지금까지 상대방이 말한 소수중에서 3번째로 큰 수만큼 점수를 얻게 된다.(만약 상대방이 지금까지 말한 소수가 3개 미만이라면 상대방은 1000점을 얻게 된다.) 만약 지금까지 한번이라도 등장한 소수를 말할 경우 해당 소수를 말한 팀이 -1000을 얻게 되며 해당 소수는 그 사람이 말한 소수로 기록되지 않는다. 규성이는 도전자이므로 게임은 항상 대웅이부터 시작한다. 두 사람이 말할 수 있는 소수는 항상 5000000 미만이다. 다음과 같은 규칙으로 소수 게임을 진행할 때 승자를 출력하시오.

입력

입력의 첫째 줄에 두 사람이 대결을 하는 라운드 수 N이 주어진다. (5≤N≤100,000)

이 후 N개의 줄에 대웅이와 규성이가 말하는 정수가 공백으로 구분되어 주어진다. 두 사람이 말하는 정수는 5,000,000보다 작은 자연수 또는 0이다.

출력

대웅이가 이길 경우 “소수의 신 갓대웅” 규성이가 이길 경우 “소수 마스터 갓규성”을 출력한다. 만약 비길 경우 “우열을 가릴 수 없음” 을 출력한다.

예제 입력 

5
2 3
4 9
2 10
7 37
11 3

예제 출력 

소수의 신 갓대웅

해설 및 후기

우선 최대 정수의 크기가 주어졌으므로 해당 크기만큼 에라토스테네스의 체를 이용하여 소수 판별이 가능하도록 한다. 다음으로 최대 힙(최소 힙의 변형)을 사용하여 소수게임의 규칙 “2. 상대방이 말한 소수 중에서 3번째로 큰 수만큼 전수를 얻게 된다.”를 처리할 수 있도록 한다. 또한 in을 이용해 해당 소수가 사용되었는지를 판별하는 것이 아닌 에라토스테네스의 체 자체에서 사용 여부를 판별할 수 있도록 하여 O(1)시간으로 사용 여부를 판별할 수 있도록 한다.

제출 코드 

import heapq as h
import sys

era = [[False, False] for _ in range(5000001)]
era[0][0] = True
era[1][0] = True
a = 0
b = 0

for i in range(2, int(5000000**0.5)+1):
    if(era[i][0]):
        continue
    tmp = 2
    while(tmp*i <= 5000000):
        era[tmp*i][0] = True
        tmp += 1


n = int(sys.stdin.readline().rstrip())

heapA = []
heapB = []

def getNum(hp): #상대가 얻는 점수
    if(len(hp)<3):
        return 1000
    h1 = h.heappop(hp)
    h2 = h.heappop(hp)
    h3 = h.heappop(hp)
    h.heappush(hp,h1)
    h.heappush(hp,h2)
    h.heappush(hp,h3)
    return h3*-1

for i in range(n):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    if(not era[x][0] and not era[x][1]): #소수이며 첫 번째로 사용
        h.heappush(heapA, x*-1)
        era[x][1] = True
    else:
        if(era[x][0]): #소수가 아님
            b += getNum(heapB)
        else:
            a -= 1000
    
    if(not era[y][0] and not era[y][1]):
        h.heappush(heapB, y*-1)
        era[y][1] = True
    else:
        if(era[y][0]):
            a += getNum(heapA)
        else:
            b -= 1000

if(a>b):
    print('소수의 신 갓대웅')
elif(a<b):
    print("소수 마스터 갓규성")
else:
    print("우열을 가릴 수 없음")