[프로그래머스] 소수 만들기

문제설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.
  
  

해결 방법

DFS로 주어진 수를 3개 뽑아 만들 수 있는 모든 조합을 찾고, 찾은 수가 소수가 되는지 판별한다.

 

JAVA

package programmers;

import java.util.*;

public class p_12977 {
	static int cnt;
	public static void dfs(int x, int sum, int depth, int[] a, int[] visit) {
		if(depth == 3) {
			int flag = 0;
			for(int i = 2; i <= Math.sqrt(sum); i++) {
				if(sum % i == 0) {
					flag = 1;
					break;
				}
			}
			if(flag == 0) cnt++;
			visit[x] = 0;
			return;
		}
		
		if(x == a.length - 1) return;
		dfs(x + 1, sum + a[x + 1], depth + 1, a, visit);
		dfs(x + 1, sum, depth, a, visit);
	}
	
	public static int solution(int[] a) {
		int[] visit = new int[a.length];
		cnt = 0;
		dfs(0, a[0], 1, a, visit);
		dfs(0, 0, 0, a, visit);
		return cnt;
	}
	
	public static void main(String[] args) {
		int[] a1 = {1,2,3,4};
		int[] a2 = {1,2,7,6,4};
		
		System.out.println(solution(a2));
	}
}