백준 1017번 문제(소수 쌍) 파이썬(Python) 풀이 [로밍맨]

문제 링크

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

1017번: 소수 쌍

 

정답 코드는 아래와 같습니다.

import sys
import collections
import math
 
VMAX = 52
SOURCE = 50
SINK = 51
NN = 2000
 
primes = [True] * (NN)
primes[1] = False
for i in range(2, NN):
  if primes[i]:
    for j in range(i*2, NN, i):
      primes[j] = False
 
def isPrime(val):
  return primes[val]
 
def bfs(flow, capacity, source, sink):
  parent = [-1] * VMAX
  q = collections.deque([source])
  parent[source] = source
  while len(q) != 0:
    item = q.popleft()
    for i in range(VMAX):
      if parent[i] == -1 and capacity[item][i] - flow[item][i]:
        q.append(i)
        parent[i] = item
  return parent
 
def maxFlow(capacity, source, sink, flow):
  rst = 0
  while True:
    parent = bfs(flow, capacity, source, sink)
    if parent[sink] == -1:
      return rst
    #minimum
    node = sink
    m = math.inf
    while node != source:
      m = min(m, capacity[parent[node]][node] - flow[parent[node]][node])
      node = parent[node]
    #add
    rst += m
    node = sink
    while node != source:
      flow[parent[node]][node] += m
      flow[node][parent[node]] -= m
      node = parent[node]
 
def solve():
  n = int(sys.stdin.readline().rstrip())
  arr = list(map(int, sys.stdin.readline().rstrip().split()))
  even = []
  odd = []
  for i in range(n):
    if arr[i] % 2 == 0:
      even.append(i)
    else:
      odd.append(i)
  # build graph
  graph = [[0] * VMAX for _ in range(VMAX)]
  for i in even:
    graph[SOURCE][i] = 1
  for i in odd:
    graph[i][SINK] = 1
  for i in even:
    for j in odd:
      if isPrime(arr[i] + arr[j]):
        graph[i][j] = 1
  rst = []
  while True:
    flow = [[0] * VMAX for _ in range(VMAX)]
    val = maxFlow(graph, SOURCE, SINK, flow)
    if val == n // 2:
      if arr[0] % 2 == 0: # even 
        for i in odd:
          if flow[0][i] == 1:
            rst.append(arr[i])
            graph[0][i] = 0
      else:
        for i in even:
          if flow[i][0] == 1:
            rst.append(arr[i])
            graph[i][0] = 0
    else:
      break
  if len(rst) == 0:
    print(-1)
  else:
    rst.sort()
    for item in rst:
      print(item, end = ' ')
    print("")
 
solve()
 

 

728x90

 

숨은 조건을 찾는 것이 이 문제를 푸는데 상당히 중요하게 작용합니다.

숨은 조건이란, 중복하지 않는 자연수의 합으로 만들 수 있는 소수는 홀수밖에 없으며,

두 수를 더해서 홀수가 되기 위해서는 반드시 하나는 짝수이고, 다른 하나는 홀수여야 한다는 것입니다.

이것을 알아내기만 한다면, 소수 구하기와 이분매칭을 공부하신 분이라면 어렵지 않게 풀 수 있는 문제입니다.

소수 구하기: https://roamingman.tistory.com/70

이분 매칭: https://roamingman.tistory.com/19

 

다만, 과연 실전에서 이런 숨은 조건을 잘 찾아낼 수 있을지는 생각해 봐야할 문제입니다.

다른 문제 풀이를 하면서, 풀이가 떠오르지 않을 때 어떻게 해야 좋을지에 대해서 제가 써 놓은 글이 있습니다.

학습하시는데 참고가 되길 바랍니다.

https://roamingman.tistory.com/46

 

풀이는 아래 영상을 참고 바랍니다.

https://www.youtube.com/watch?v=sAzFsEoLPko 

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)