BOJ 1017 : 소수 쌍

문제 링크 : https://www.acmicpc.net/problem/1017

 

보는 순간 바로 이분매칭이 떠오른다.

하지만 이분매칭은 기본적으로 이분그래프에서 이루어져야 하기 때문에 한 번 막혔었다.

 

서로 다른 두 수의 합으로 생성된 소수는 무조건 홀수가 될 수 밖에 없다.

또한, 홀수는 무조건 (홀수 + 짝수) 로 만들어질 수 밖에 없다.

따라서, 이 문제는 홀수 / 짝수로 이분그래프를 형성하여 풀면 된다.

 

다만, 타 문제들과는 달리 첫 수와 매칭될 수 있는 수를 찾아야하기 때문에,

2 ~ N 번째 수와 1번째 수를 수동으로 매칭시킨 후 이분매칭을 실시하면 된다.