[devmoon] 프로그래머스 - (Java) 소수 만들기

https://programmers.co.kr/learn/courses/30/lessons/12977

코딩테스트 연습 - 소수 만들기

1. 유형

수학, 조합

 

2. 시뮬레이션

 

• 에라토스테네스의 체 소수판단
• 조합

배열에서 3개를 선택하면 그 합이 소수인지 판단하면 된다.

소수판단은 효율성을 생각해서 에라토스테네스의 체를 사용한다

 

3. 코드

class Solution {
    static boolean matrix[];
    static int Nums[];
    static int ans=0;
    public int solution(int[] nums) {
        int answer = -1;
        matrix = new boolean[3001];
        Nums = nums;
        matrix[1] = true;
        isPrime();
        comb(0,0,0);
        answer = ans;
        return answer;
    }
    static void isPrime(){
        for(int i=2; i<=3000; i++){
            if(matrix[i]) continue;
            int index = 2;
            while(i*index<=3000){
                matrix[i*index] = true;
                index++;
            }
        }
    }
    static void comb(int depth, int pick,int sum){
        if(pick == 3){
            if(!matrix[sum]){
                ans++;
            }
            return;
        }
        if(depth == Nums.length){
            return;
        }
        comb(depth+1, pick+1, sum+Nums[depth]);
        comb(depth+1, pick, sum);
    }
}