boj 1017 : 소수 쌍
https://www.acmicpc.net/problem/1017
1017번: 소수 쌍
지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 그룹지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11
www.acmicpc.net
풀이중....
대략 이런느낌이다.
예제의 {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. 찾은 값들을 정렬하여 출력한다.
이분매칭 코드는... 아무래도 좀더 다듬을 수 있을 것 같다.