boj 1017 : 소수 쌍

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

1017번: 소수 쌍

 

풀이중....

 

대략 이런느낌이다.

예제의 {1, 4, 7, 10, 11, 12} 에서

{1, x} 에서 x를 1과 짝지었을 때 소수가 되는 수라고 할 때,

{1, 4, 7, 10, 11, 12} - {1, x} 에서 각 쌍의 합을 소수로 만들 수 있는 모든 x를 출력한다.

 

각 쌍의 합을 소수로 만들 수 있는지 확인하는 작업은 이분매칭과 유사한 방법등으로 시간 내에 가능한 알고리즘이 있겠지만,

알고리즘의 세계를 떠난 지가 너무 오래되어 방법이 떠오르지 않으니...  (사실 이분매칭이 무엇이었는지도 기억이 나지 않는다.)

충분한 시간을 들여 고민 후 차후에 상세 풀이를 올리도록 하겠다.

 

 

 

위와 같은 이분 그래프에서 모든 쌍이 매칭되는지를 묻는 이분매칭 문제로 치환하여 해결할 수 있다.

예제의 {1, 4, 7, 10, 11, 12} 에서 {1,x} 매칭을 고정한 후, 나머지가 모두 매칭되는지를 확인하면 된다.

 

1. 에라토스테네스의 체를 통해 2000까지의 소수를 구함.

2. A0 + Ax 가 소수일 때, {A0, Ax}를 제외한 나머지가 모두 매칭되는 Ax를 모두 찾는다.

3. 찾은 값들을 정렬하여 출력한다.

 

코드

이분매칭 코드는... 아무래도 좀더 다듬을 수 있을 것 같다.