[백준_19699번] 소-난다!

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

19699번: 소-난다!

[문제]

 지난 번 헛간 청약의 당첨우(牛)가 발표됐다. 청약에 당첨된 소들은 날아갈 듯이 기뻐하다가 진짜로 하늘을 날았다. 하지만 이후로 소들은 날 수 없었다. 그러던 어느 날, 꿀벌에게 쏘이면 잠깐 하늘을 날 수 있다는 사실을 깨달았다. 이 사실이 퍼지자 소들은 다시 자유롭게 하늘을 날기 시작했다.

 소들이 하늘을 날며 우(牛)통사고가 빈번해지자, 농부 존은 소들이 하늘을 나는 것에 제한을 두었다. 소들은 항의했지만 소들의 항의는 받아들여지지 않았다. 농장에는 N마리의 소가 있다. 농부 존은 소들의 몸무게의 합이 소수(prime)가 되도록 M마리의 소를 선별할 계획이다. 농부 존의 계획에 맞게 소를 선별했을 때 나올 수 있는 몸무게의 합을 모두 출력하시오.

 

[입력 조건]

• 첫째 줄에 농장에 있는 소들의 수 N, 선별할 소의 수 M이 주어진다.
• 둘째 줄에 소들의 몸무게 H가 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_19699 {
	static HashSet<Integer> set=new HashSet<>();
	static int n,m;
	static boolean[] visited;
	static int[] weight;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		weight=new int[n];
		visited=new boolean[n];
		
		for(int i=0;i<n;i++)
			weight[i]=sc.nextInt();
		
		dfs(0,0,0);
		
		// 정렬을 위해 HashSet의 데이터를 연결리스트에 복산
		ArrayList<Integer> result=new ArrayList<>(set);
		Collections.sort(result); // 정렬
		
		// 소들의 몸무게 합으로 만들 수 있는 소수가 없는 경우
		if(result.size()==0)
			System.out.println(-1);
		// 소들의 몸무게 합으로 만들 수 있는 소수가 있다면 출력
		else {
			for(int i=0;i<result.size();i++)
				System.out.print(result.get(i)+" ");
		}
	}
	
	// 백트래킹
	static void dfs(int depth, int sum, int start) {
		// m마리의 소를 선택했다면 몸무게의 합이 소수인지 판별
		if(depth==m) {
			if(isPrime(sum))
				set.add(sum); // 몸무게의 합이 소수라면 HashSet에 몸무게 삽입 
			return;
		}
		
		// 중복된 경우의 수를 제거하기 위해 start 부터 탐색
		for(int i=start;i<n;i++) {
			if(!visited[i]) {
				visited[i]=true;
				dfs(depth+1,sum+weight[i],i+1);
				visited[i]=false;
			}
		}
	}
	
	// 에라토스테네스의 채로 소수 판별
	static boolean isPrime(int num) {
		for(int i=2;i<=Math.sqrt(num);i++) {
			if(num%i==0)
				return false;
		}
		return true;
	}
}

 

[고찰] 

 이번 문제는 백트래킹과 에라토스테네스의 채 알고리즘을 사용하여 해결하였다. 먼저 백트래킹을 사용하여 n마리의 소 중 m마리를 선택했고, 선택한 소들의 몸무게의 합을 구한뒤 에라토스테네스의 채 알고리즘을 통해 구한 몸무게가 소수인지 판별하였다.

 소를 선택하는 과정에서 (1번, 3번, 5번) 소를 선택한 경우와 (3번, 1번, 5번)을 선택한 경우는 같기 때문에 start 변수를 사용하여 이전에 선택한 소는 더이상 선택할 수 없게 해주었다. 또한 소의 몸무게의 합에는 중복이 없어야 하므로 HashSet에 값을 저장한 후 정렬을 위해 연결리스트에 데이터를 복사해주었다.