#1017 소수쌍(네트워크 플로우)

처음 이 문제를 접했을 때에는 '혹시 쌍둥이 소수' 문제일까 하고 봤었네요.  소수쌍이 아니라 합이 소수가 되는 숫자들의 합 이야기입니다.  짝수인 N개가 주어지면, 합이 소수가 되는 쌍으로 모두 묶을 수 있다면, 첫번째 수와 묶일 수 있는 수들의 리스트를 내는 문제입니다.  난이도는 Platinum III이지만, 난이도보다는 쉬운 문제입니다.  물론 네트워크 플로우 알고리즘을 알고 있을 때에 한합니다.  DFS 알고리즘으로도 풀 수 있지만, 그렇게 하면 시간초과가 납니다.

 

 

아래는 해당 문제의 링크입니다.

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

1017번: 소수 쌍

 

이 문제에서는 소수를 빨리 찾는 방법이 관건입니다.  리스트에 있는 수들의 50개이므로, 첫번째수와 연결되는 두번째 수를 선택하고 나머지에 대해서 소수쌍이 되는지 검사하면 됩니다.  미리 매칭 테이블을 만들어놓아서 한다면, 최대 \(25 \times 49=1225\)번의 소수 검사만 하면 됩니다.  나올 수 있는 소수 크기가 2,000 미만이므로 소수 검사비용도 상당히 저렴합니다.

 

알고리즘은 간단합니다.

첫번째 수는 당연히 필요한 것이고, 두번째 수를 차례대로 선택한 후, 이 합이 소수이면, 나머지 수들에 대해서는 네트워크플로우를 이용해서 소수쌍으로 모든 수들이 참여가능한지 판단합니다.  그렇게 판단이 되면 두번째 수를 출력하고 이 과정을 반복하면 됩니다.

 

network flow algorithm

 

제가 작성한 소스입니다.

//----------------------------------------------------------
//    baekjoon #1017 - Prime Pairs
//        - by Aubrey Choi
//        - created at 2019-05-20
//----------------------------------------------------------
#include <stdio.h>
#include <memory.h>

static unsigned char primes[] = {
    0xac,0x28,0x8a,0xa0,0x20,0x8a,0x20,0x28,    0x88,0x82,0x08,0x02,0xa2,0x28,0x02,0x80,
    0x08,0x0a,0xa0,0x20,0x88,0x20,0x28,0x80,    0xa2,0x00,0x08,0x80,0x28,0x82,0x02,0x08,
    0x82,0xa0,0x20,0x0a,0x20,0x00,0x88,0x22,    0x00,0x08,0x02,0x28,0x82,0x80,0x20,0x88,
    0x20,0x20,0x02,0x02,0x28,0x80,0x82,0x08,    0x02,0xa2,0x08,0x80,0x80,0x08,0x88,0x20,
    0x00,0x0a,0x00,0x20,0x08,0x20,0x08,0x0a,    0x02,0x08,0x82,0x82,0x20,0x0a,0x80,0x00,
    0x8a,0x20,0x28,0x00,0x22,0x08,0x08,0x20,    0x20,0x80,0x80,0x20,0x88,0x80,0x20,0x02,
    0x22,0x00,0x08,0x20,0x00,0x0a,0xa0,0x28,    0x80,0x00,0x20,0x8a,0x00,0x20,0x8a,0x00,
    0x00,0x88,0x80,0x00,0x02,0x22,0x08,0x02,    0x80,0x08,0x82,0x80,0x20,0x00,0x22,0x28,
    0x80,0x82,0x00,0x0a,0xa0,0x20,0x00,0x80,    0x28,0x82,0x20,0x20,0x08,0x02,0x00,0x80,
    0x02,0x08,0x08,0x20,0x08,0x02,0x02,0x20,    0x82,0xa0,0x20,0x00,0x02,0x08,0x00,0xa0,
    0x08,0x0a,0xa2,0x08,0x80,0x82,0x00,0x00,    0x00,0x00,0x82,0x20,0x20,0x00,0x80,0x00,
    0x02,0x80,0x28,0x82,0x80,0x28,0x08,0x80,    0x00,0x8a,0x22,0x08,0x80,0x00,0x08,0x08,
    0x80,0x20,0x82,0x80,0x08,0x88,0x00,0x20,    0x82,0x22,0x28,0x08,0x20,0x00,0x00,0x82,
    0x28,0x00,0x00,0x20,0x0a,0x20,0x00,0x0a,    0x20,0x20,0x08,0x82,0x00,0x00,0x82,0x28,
    0x00,0x02,0x08,0x80,0x80,0x00,0x80,0x00,    0x20,0x88,0xa2,0x00,0x02,0x20,0x08,0x02,
    0x00,0x28,0x00,0xa0,0x00,0x00,0x20,0x08,    0x08,0xa2
};
inline bool isprime(int p) { return (bool)((primes[p / 8] >> (p % 8)) & 1); }
char b[25], v[25], adj[25][26]; int n;
bool dfs(int s)
{
    v[s] = 1;
    for(int i = 1; i <= adj[s][0]; i++)
    {
        int t = adj[s][i];
        if(b[t] == -1 || (v[b[t]] == 0 && dfs(b[t])))
        {
            b[t] = s;
            return true;
        }
    }
    return false;
}
bool checkmatch(int s, int n)
{
    memset(b, 0xff, sizeof(b));
    b[s] = 0;
    for(int i = 1; i < n; i++)
    {
        memset(v, 0, sizeof(v));
        v[0] = 1;
        if(!dfs(i)) return false;
    }
    return true;
}
int main()
{
    int l[25], r[25], lcount = 1, rcount = 0, t, i, j;

    scanf("%d%d",&n,&l[0]);
    for(i=1;i<n;i++) { scanf("%d",&t); if((t+l[0])%2) r[rcount++]=t; else l[lcount++]=t; }
    if(lcount != rcount) { puts("-1"); return 0; }

    //    check primes between elements.
    for(i = 0; i < lcount; i++)
    {
        int count = 0;
        for(j = 0; j < lcount; j++)
        {
            if(isprime(l[i] + r[j])) adj[i][++count] = j;
        }
        adj[i][0] = count;
        if(!count) { puts("-1"); return 0; }
    }

    int ans[100], count = 0;
    for(i=1;i<=adj[0][0];i++)
    {
        int s = adj[0][i];
        if(checkmatch(s, lcount))
        {
            int last = count++;
            while(last > 0 && ans[last-1] > r[s])
            {
                ans[last] = ans[last-1];
                last--;
            }
            ans[last] = r[s];
        }
    }

    if(count == 0) { puts("-1"); return 0; }
    for(i = 0; i < count; i++) printf("%d ", ans[i]); putchar('\n');
}