소수 만들기

문제

주어진 배열 nums[]에서 3가지 수를 선택하는 경우에서 그 수들의 합이 소수가 되는 횟수를 구하는 문제.

풀이

class Solution {
    static int[] ch;
    static int answer=0;
    public int solution(int[] nums) {
        ch = new int[nums.length];
        DFS(0,0,0,nums);
        return answer;
    }
    
    public static boolean isPrime(int sum){
        if(sum==1) return false;
        else{
            for(int i=2; i<sum; i++){
                if(sum%i==0) return false;
            }
        }
        return true;
    }
    
    public static void DFS(int L,int s,int sum,int[] nums){
        if(L==3){
            if(isPrime(sum)==true) answer++;
            return;
        }
        else{
            for(int i=s; i<nums.length; i++){
                if(ch[i]==0){
                    ch[i]=1;
                    DFS(L+1,i+1,sum+nums[i],nums);
                    ch[i]=0;
                }
            }
        }
    }
}

일단 경우의수 관련 문제는 DFS()로 푸는게 편하다. 겹치면 안되기에 DFS()를 재귀호출할때 스타트지점 s만 +1 시켜주면 겹치지 않게 경우의 수 구하는게 가능하다.
isPrime 함수를 만들어서 소수를 판별했다.