[백준] 25632번: 소수 부르기 게임

문제

백준 - 25632번: 소수 부르기 게임

분석

용태와 유진이가 부를 수 있는 소수 범위가 각각 주어지고, 용태부터 번갈아가며 소수를 부른다고 할 때, 누가 이길지 판별하는 문제이다.

각자 최선을 다한다고 하면 공통된 범위의 소수를 먼저 부르는게 이득이다.
따라서 각자 부를 수 있는 소수를 구하고, 공통된 소수개수를 뺐을 때 누가 더 많은지 확인하면 된다. 만약 같다면 공통된 소수의 개수가 홀수인지 짝수인지에 따라 달라진다.
용태가 먼저 시작하기 때문에 홀수면 용태가 이기고 짝수면 유진이 이긴다.

여러개의 소수를 구할 때는 에라토스테네스의 체를 이용하면 된다.
처음에 최대 범위만큼의 크기로 배열을 생성한다. (소수라고 초기화한다.)
2부터 진행하는데, 범위 최대값의 제곱근까지만 진행해도 된다. (제곱근이 넘어가면서는 이미 판별이 됐기 때문)
이미 소수가 아니라한 경우는 넘어가고, 소수인 경우에 관련 배수들을 모두 False 처리한다.
마지막에 True인 것들만 리스트에 담으면 소수를 얻을 수 있다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

a, b = map(int, input().split())
c, d = map(int, input().split())
MAX = 1000
def genPrimary():
    arr = [True]*(MAX+1)
    for i in range(2, int(MAX**0.5)+1):
        if not arr[i]:
            continue
        for j in range(i*i, MAX+1, i):
            arr[j] = False
    return [i for i in range(2, MAX+1) if arr[i]]

primes = genPrimary()
yt = [elem for elem in primes if a <= elem <= b]
yj = [elem for elem in primes if c <= elem <= d]
joint = list(set(yt) & set(yj))
yt_size = len(yt)-len(joint)
yj_size = len(yj)-len(joint)
if yt_size > yj_size:
    print('yt')
elif yt_size < yj_size:
    print('yj')
else:
    if len(joint)%2:
        print('yt')
    else:
        print('yj')

끝으로..

이번에 에라토스테네스의 체를 다시 공부해서 상기시켰다.