본문 바로가기

카테고리 없음

[백준 1017번] 소수 쌍 (Python3)

def sieve():
  prime = set(); check = [0]*2000
  for n in range(2,2000):
    if check[n]:
      continue
    prime.add(n)
    for n in range(n,2000,n):
      check[n] = 1
  return prime

def DFS(i):
  if visited[i]:
    return
  visited[i] = 1
  for e in graph[i]:
    if not match[e]:
      match[e] = i
      return 1
  for e in graph[i]:
    if DFS(match[e]):
      match[e] = i
      return 1

def solve():
  global visited
  for i in range(2,N):
    visited = [0]*N; visited[1] = 1
    if not DFS(i):
      return
  return 1

input()
nums = [*map(int,input().split())]
even = [0]; odd = [0]
for n in nums:
  if n%2:
    even.append(n)
  else:
    odd.append(n)
if nums[0]%2:
  even,odd = odd,even
N = len(odd); result = []
if N==len(even):
  graph = [[] for i in range(N)]
  prime = sieve()
  for i in range(1,N):
    for j in range(1,N):
      if odd[i]+even[j] in prime:
        graph[i].append(j)
  for r in graph[1]:
    match = [0]*N; match[r] = 1
    if solve():
      result.append(even[r])
print(*sorted(result) if result else [-1])

이분매칭 응용문제

서로 다른 두 수의 합으로 소수를 만들려면 반드시 두 수 중 하나는 짝수 하나는 홀수여야함을 이용하는 문제이다.

 

풀이를 설명하면,

1. 에라토스테네스의 체 방식으로 1~2000 사이의 소수를 모두 구한다.

2. 짝수는 짝수끼리, 홀수는 홀수끼리 모은다. 이때 짝수와 홀수의 개수가 다르면 -1을 출력

3. 첫번째 숫자가 짝수인지 홀수인지에 따라 기준집단으로 잡고, 짝수-홀수 사이에 더했을 때 소수가 되는 경우에 그래프로 연결한다.

4. 첫번째 숫자를 연결하고 나서, 이분매칭 알고리즘으로 모든 숫자를 매칭할 수 있는지 판별하고 가능한 경우 저장한다.

5. 4에서 저장한 숫자를 오름차순으로 출력한다.

 

이분매칭이라는 사실을 적절하게 숨긴 재미있는 문제였다.

 

오늘의 교훈) 다양한 이분매칭 활용문제를 해결해보자