[JavaScript/section 8] 15 - 수들의 조합

📌 15 - 수들의 조합

N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수는 몇 개가 있는지 출력하는 문제이다.

예를 들면 5개의 숫자 2 4 5 8 12가 주어지고, 3개를 뽑은 조합의 합이 6의 배수인 조합을 찾으면 4+8+12, 2+4+12로 2가지가 있다.

 

📝 풀이 방법

😵 나의 풀이 방법

if문 안에 2개의 조건을 같이 주어 L(레벨)이 k(뽑는 개수)와 같더라도 sum이 6의 배수가 아니라면 else문으로 이동한다. 이 과정에서 결과는 동일하게 나오지만 시간을 잡아먹을 수 있다.🤬

L이 k와 같다면 else 문으로 이동하는 것이 아닌 if문 내부에서 sum이 6의 배수인지를 확인하고 빠져나와야 한다.

function solution(n, k, arr, m) {
  let answer = 0;

  function DFS(L, s, sum) {
    if (L === k && sum % m === 0) {
      answer++;
    } else {
      for (let i = s; i < n; i++) {
        DFS(L + 1, i + 1, sum + arr[i]);
      }
    }
  }

  DFS(0, 0, 0);
  return answer;
}

let arr = [2, 4, 5, 8, 12];
console.log(solution(5, 3, arr, 6));

 

👍 강사님 풀이 방법

• L이 k와 같다면 하나의 경우가 만들어진 것이므로 sum이 6의 배수인지 확인한다.
• L이 k와 같고 sum이 6의 배수라면 answer++을 해준다.

function solution(n, k, arr, m) {
  let answer = 0;

  function DFS(L, s, sum) {
    if (L === k) {
      if (sum % m === 0) answer++;
    } else {
      for (let i = s; i < n; i++) {
        DFS(L + 1, i + 1, sum + arr[i]);
      }
    }
  }

  DFS(0, 0, 0);
  return answer;
}

let arr = [2, 4, 5, 8, 12];
console.log(solution(5, 3, arr, 6));