프로그래머스 소수 만들기

문제

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

프로그래머스

접근

1) 주어진 수 n(숫자 배열의 길이) 개 중 3개의 수를 골라 합을 만드는 경우의 수 -> 조합문제, dfs

2) 합이 소수인지 확인한다. (아래 isPrime 함수를 이용한다.)

3) 소수라면 경우의 수 +1 을 한다.

풀이

function isPrime(num) {
  for (let i = 2, s = Math.sqrt(num); i <= s; i++) {
    if (num % i === 0) return false;
  }
  return num > 1;
}

function solution(nums) {
  const N = nums.length;
  const M = 3;
  const checked = Array(N).fill(false);
  let sum = 0;
  let answer = 0;

  function dfs(level, start) {
    if (level === M) {
      if (isPrime(sum)) answer++;
      return;
    }

    for (let i = start; i < N; i++) {
      if (checked[i]) continue;

      checked[i] = true;
      sum += nums[i];
      dfs(level + 1, i);
      sum -= nums[i];
      checked[i] = false;
    }
  }

  dfs(0, 0);

  return answer;
}