게임이론 배우기 -소수 부르기 게임-

1. 문제

 

25632번: 소수 부르기 게임 (acmicpc.net)

25632번: 소수 부르기 게임

 

2. 풀이1

 

두 플레이어가 주어진 범위 a,b와 c,d에서 각각 소수를 찾는다

 

만약 승리를 위해 최선을 다해서 플레이한다면, 어떻게 해야 할까

 

핵심 규칙은 이미 부른 소수는 부르지 못한다는 것이다

 

그러므로 상대가 가지고 있는 소수를 내가 먼저 부른다면, 상대가 가지고 있는 소수를 부르지 못하게 하면서 동시에 나는 턴을 넘기므로 매우 유리해진다

 

따라서 두 플레이어가 가지고 있는 소수 집합에서 공통된 소수 집합도 찾아야겠다

 

from sys import stdin

def get_prime(a,b):
    
    result = []
    
    for n in range(a,b+1):
        
        prime = True

        for i in range(2,int((n+1)**(1/2))+1):
            
            if n % i == 0:
                
                prime = False
                break
        
        if prime:
            
            result.append(n)
    
    return result

a,b = map(int,stdin.readline().split())

c,d = map(int,stdin.readline().split())

yt = get_prime(a,b)
yj = get_prime(c,d)

common = []

for p in yt:
    
    if p in yj:
        
        common.append(p)

 

 

수의 범위가 2~1000이라 굳이 에라토스테네스의 체를 사용하지 않고 제곱근 판정법으로 구했다

 

그리고 하나의 리스트에서 소수를 순회해서 다른 집합에도 존재하는 소수라면 공통된 집합 리스트에 넣어준다

 

다음 실제로 시뮬레이션으로 게임을 해본다

 

최적의 전략은 공통된 집합에 존재하는 소수를 먼저 부르는 것이다

 

그리고 소수 크기에 상관없이 어떤 소수를 부르든지는 상관 없다

 

가지고 있는 소수 아무거나 부르면 되겠다

 

prime_list = []

turn = 0

winner = 0

while 1:
    
    success = False

    while common:
        
        p = common.pop()
        
        prime_list.append(p)

        success = True
        break
    
    
    if success:
        
        turn += 1
        turn %= 2

 

공통된 소수를 먼저 불러서, pop()을 성공적으로 수행했다면, 이미 부른 소수들의 집합 prime_list에 넣어주고

 

success를 True로 바꿔줌

 

그리고 다음 턴으로 넘겨준다

 

근데 공통된 소수 집합이 비어서 공통된 소수를 성공적으로 부르지 못했을 수가 있어

 

그러면 success는 False인데

 

이제 turn이 0이냐 1이냐에 따라 행동이 달라지지

 

    if success == False:
        
        if turn == 0:
            
            while yt:
                
                p = yt.pop()

                if p not in prime_list:
                    
                    prime_list.append(p)
                
                    success = True
                    break
            
            if success == False:
                
                winner = 1
                break
        
        else:
            
            while yj:
                
                p = yj.pop()

                if p not in prime_list:
                    
                    prime_list.append(p)
                
                    success = True
                    break
            
            if success == False:
                
                winner = 0
                break

 

turn이 0이면 용태가 가지고 있는 소수 집합에서 하나를 빼서 불러보는데

 

소수를 부를때는 이미 부른 소수는 부를 수 없으므로 prime_list에 존재하는지 아닌지를 검사

 

이미 존재하면 다시 pop해야하고

 

존재하지 않으면 prime_list에 넣어주고 success를 True로 바꿔준다

 

그리고 한번만 성공하면 되니까 바로 break

 

가지고 있는 모든 소수를 pop했는데도 success가 False이면 소수를 부르지 못했으므로 패배

 

turn이 1일때는 용태에서 유진이로 바뀌는 것 뿐이다

 

winner값에 따라 승자를 출력

 

from sys import stdin

def get_prime(a,b):
    
    result = []
    
    for n in range(a,b+1):
        
        prime = True

        for i in range(2,int((n+1)**(1/2))+1):
            
            if n % i == 0:
                
                prime = False
                break
        
        if prime:
            
            result.append(n)
    
    return result

a,b = map(int,stdin.readline().split())

c,d = map(int,stdin.readline().split())

yt = get_prime(a,b)
yj = get_prime(c,d)

common = []

for p in yt:
    
    if p in yj:
        
        common.append(p)


prime_list = []

turn = 0

winner = 0

while 1:
    
    success = False

    while common:
        
        p = common.pop()
        
        prime_list.append(p)

        success = True
        break
    
    if success == False:
        
        if turn == 0:
            
            while yt:
                
                p = yt.pop()

                if p not in prime_list:
                    
                    prime_list.append(p)
                
                    success = True
                    break
            
            if success == False:
                
                winner = 1
                break
        
        else:
            
            while yj:
                
                p = yj.pop()

                if p not in prime_list:
                    
                    prime_list.append(p)
                
                    success = True
                    break
            
            if success == False:
                
                winner = 0
                break
    
    if success:
        
        turn += 1
        turn %= 2


if winner == 1:
    
    print('yj')

else:
    
    print('yt')

 

 

3. 풀이2

 

게임이론의 묘미는 사실 시뮬레이션 하지 않고도 정답을 알아내는 것에 있다

 

게임의 최적 전략은 이미 알아낸 것 처럼 

 

"상대가 가지고 있는 소수를 먼저 부른다"이다

 

근데, 그 이전에 이 게임은 소수 크기에 상관없이 가지고 있는 소수 어떤 것이든 부르지 않았던 소수는 그냥 부를수가 있다

 

그니까 애초에 상대방보다 소수를 더 많이 가지고 있으면 내가 언제 시작하든지 간에 무조건 게임에서 이길 수 있다

 

A가 2 3 5

 

B가 2 3 5 7이면...

 

A가 먼저 시작해도 2_A, 3_B, 5_A, 7_B로 B의 승리

 

B가 먼저 시작해도 2_B, 3_A, 5_B로 B의 승리

 

아예 중복이 안된다고 해도 

 

A가 2,3,5

 

B가 7,11,13,15

 

A가 먼저 시작해도 2, 7, 3, 11, 5, 13으로 B의 승리

 

B가 먼저 시작해도 7, 2, 11, 3, 13, 5, 15로 B의 승리

 

근데 두 플레이어가 가지고 있는 소수의 개수가 같다면 조금 생각해야겠다

 

당연히 최적의 전략은 "상대가 가지고 있는 소수를 먼저 부른다"이다

 

A가 먼저 시작할때

 

만약 공통된 소수가 홀수개이면?

 

A,B,A,B,A,B,A,...로 진행되니까

 

자기만 가지고 있는 카드를 먼저 써야하는 플레이어는 B가 된다

 

그러므로 A가 자기만 가지고 있는 카드가 B보다 더 많다

 

그래서 A가 반드시 승리한다

 

공통된 소수가 짝수개이면?

 

A,B,A,B,...로 진행되니까

 

자기만 가지고 있는 카드를 먼저 써야하는 플레이어는 A가 된다

 

그러므로 B가 자기만 가지고 있는 카드가 A보다 많다

 

따라서 B가 반드시 승리하게 된다

 

from sys import stdin

def get_prime(a,b):
    
    result = []
    count = 0
    
    for n in range(a,b+1):
        
        prime = True

        for i in range(2,int((n+1)**(1/2))+1):
            
            if n % i == 0:
                
                prime = False
                break
        
        if prime:
            
            result.append(n)
            count += 1
    
    return result,count

a,b = map(int,stdin.readline().split())

c,d = map(int,stdin.readline().split())

yt,p = get_prime(a,b)
yj,q = get_prime(c,d)

common = []
r = 0

for n in yt:
    
    if n in yj:
        
        common.append(n)
        r += 1

if p > q:
    
    print('yt')

elif p < q:
    
    print('yj')

else:

    if r % 2 == 1:
        
        print('yt')
    
    else:
        
        print('yj')

 

 

공통된 소수 멋있게 찾아볼려다가 삽질 너무 많이함...

 

분명 제대로 구한것 같았는데