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

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

 

소요시간 : 10분

 

그냥 조합 + 소수

 

소수는 2 부터 num-1 까지 다 나눠보다가 나머지 0인 거 있으면 소수가 아닌 수.

조합은 그냥 조합코드.

처음에 cnt == N 으로 잘못 적어서 어버버함

class Solution {
  public int solution(int[] nums) {
    N = nums.length;
    selected = new boolean[N];
    combi(0, 0, nums);
    return answer;
  }

  boolean isPrime(int num) {
    for (int i = 2; i < num; i++) {
    	if(num % i == 0) return false;
    }
    return true;
  }

  int answer = 0;
  int N;
  boolean[] selected;
  void combi(int start, int cnt, int[] nums) {
    if(cnt == 3) {
      int sum = 0;
      for (int i = 0; i < N; i++) {
      	if(selected[i]) sum += nums[i];
      }
      if(isPrime(sum)) answer++;
      return;
    }

    for (int i = start; i < N; i++) {
      selected[i] = true;
      combi(i+1, cnt+1, nums);
      selected[i] = false;
    }
  }
}