[BOJ] 백준 1017번 소수 쌍 (Java)

#1017 소수 쌍

난이도 : 플레 3

유형 : 소수 / 이분 매칭

1017번: 소수 쌍

▸ 문제

지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 짝지을 수 있다.

1 + 4 = 5, 7 + 10 = 17, 11 + 12 = 23

또는

1 + 10 = 11, 4 + 7 = 11, 11 + 12 = 23

수의 리스트가 주어졌을 때, 지민이가 모든 수를 다 짝지었을 때, 첫 번째 수와 어떤 수를 짝지었는지 오름차순으로 출력하는 프로그램을 작성하시오. 위의 예제에서 1 + 12 = 13으로 소수이다. 그러나, 남은 4개의 수를 합이 소수가 되게 짝지을 수 있는 방법이 없다. 따라서 위의 경우 정답은 4, 10이다.

▸ 입력

첫째 줄에 리스트의 크기 N이 주어진다. N은 50보다 작거나 같은 자연수이며, 짝수이다. 둘째 줄에 리스트에 들어있는 수가 주어진다. 리스트에 들어있는 수는 1,000보다 작거나 같은 자연수이며, 중복되지 않는다.

▸ 출력

첫째 줄에 정답을 출력한다. 없으면 -1을 출력한다.

 

문제 풀이  

최대 50개의 크기를 가지는 수열에서 소수로 이뤄지는 최대 매칭 쌍을 구하기 위해서는 이분 매칭을 사용하면 된다. 네트워크 그래프를 구하면 O(V*E)로 구할 수 있다. 그러므로 최대 O(50* 50* 49)이 걸린다. 

 

먼저 소수가 되기 위해서는 (even, odd)의 쌍만 가능하다. 그리고 두 수는 중복이 되지 않으므로 최소의 합은 3, 최대의 합은 1999이다.

• even + even = even
• odd + odd = even
• even 짝수는 절대 소수가 될 수 없다. 짝수끼리의 최소 합은 2+4 = 6이고, 홀수끼리의 최소 합은 1+3 =4이므로 예외는 없다.

문제에서는 첫 번째 수와 짝 지어지는 수들을 원하므로 첫 번째 수가 홀수이냐 짝수이냐에 따라 리스트의 우선순위가 정해진다. 첫 번째 수 가 속한 리스트가 매칭의 주인으로 다른 리스트를 향해 이분 매칭을 이루게 된다.

• a가 첫 번째 수가 속한 리스트이고, b가 첫 번째 수가 속하지 않은 리스트이다.

int first= Integer.parseInt(st.nextToken());
a.add(first);
for(int i=1; i<n; i++) {
	int num = Integer.parseInt(st.nextToken());
	if(!(isEven(first)^isEven(num))) {
		a.add(num);
	}else {
		b.add(num);
	}
}

 

그렇게 even리스트, odd리스트를 구분하였다면 두 리스트의 사이즈는 일치해야 한다. 만약 일치하지 않으면 매칭이 되지않아 -1을 출력하고 종료하면 된다.

if(a.size() != b.size()) {
	System.out.println(-1);
	return;
}

 

이제 이 두 리스트의 합이 소수(Prime)이 되는 경우를 조사하여 이분매칭 리스트에 넣어준다. 이러면 네트워크 그래프가 형성되게 된다. 예제1번을 예로 들면 다음과 같다.

• a(i)+b(j) = prime nubmer라면 list[i].add(j);
• 1이 첫 번째 수 이므로 A 리스트는 홀수 리스트로 설정해줘야 한다.

이분매칭 그래프

 

 

이제 위에서 구한 그래프로 이분 매칭을 이뤄주면 된다. 무조건 첫 번째 수는 매칭이 되어야하며 그렇게 모든 쌍이 이뤄졌을 경우 첫 번째 수와 매칭된 수를 저장하여 출력해주면 된다. 

 

이분 매칭 자세한 내용은 여기를 참고해주세요

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {
	static final int MAX = 2000;
	static int[] apair, bpair;
	static boolean[] isPrime, check;
	static List<Integer> a, b;
	static List<Integer>[] list;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		isPrime = initPrime(MAX);
		
		a = new ArrayList<>();
		b = new ArrayList<>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		int first= Integer.parseInt(st.nextToken());
		boolean f= isEven(first);
		a.add(first);
		
		
		for(int i=1; i<n; i++) {
			int num = Integer.parseInt(st.nextToken());
			if(!(f^isEven(num))) {
				a.add(num);
			}else {
				b.add(num);
			}
		}
		if(a.size() != b.size()) {
			System.out.println(-1);
			return;
		}
		
		list = new ArrayList[a.size()];
		for(int i=0; i<a.size(); i++) {
			list[i] = new ArrayList<>();
			for(int j=0; j<b.size(); j++) {
				if(isPrime[a.get(i)+b.get(j)]) {
					list[i].add(j);
				}
			}
		}
		
		List<Integer> ans = new ArrayList<>();
		check = new boolean[a.size()];
		apair = new int[a.size()];
		bpair = new int[b.size()];
		for(int i=0; i<list[0].size(); i++) {
			int b_first = list[0].get(i);
			Arrays.fill(apair, -1);
			Arrays.fill(bpair, -1);
			apair[0] = b_first;
			bpair[b_first]=  0;
            
			int cnt = 1;
			for(int j=0; j<a.size(); j++) {
				Arrays.fill(check, false);
				if(dfs(j)) cnt++; 
			}
			if(cnt == b.size()) {
				ans.add(b.get(apair[0]));
			}
		}
		
		if(ans.size() ==0) {
			System.out.println(-1);
			return;
		}
		ans.stream().sorted().forEach(s -> System.out.print(s+" "));
	}
	
	static boolean dfs(int here) {
		for(int nxt : list[here]) {
            if(here ==0 || check[nxt]) continue;
			check[nxt] = true;	
			
			if(bpair[nxt] == -1 || dfs(bpair[nxt])) {
				apair[here] = nxt;
				bpair[nxt] = here;
				return true;
			}
		}
		return false;
	}
	
	static boolean[] initPrime(int size) {
		boolean[] isPrime = new boolean[size+1];
		Arrays.fill(isPrime, true);
		isPrime[0] = false; isPrime[1] = false;
		for(int i=2; i*i<=size; i++) {
			if(isPrime[i]) {
				for(int j=i*i; j<=size; j+=i) {
					isPrime[j] = false;
				}
			}
		}
		return isPrime;
	}
	
	static boolean isEven(int num) {
		if(num%2==0) {
			return true;
		}
		return false;
	}
}