[프로그래머스/JavaScript] 최고의 집합

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

프로그래머스

---

1) 풀이

이거 진짜 하루종일 잡고 있다가 참고자료 찾아보고 바로 풀려서 허무한 문제..

레벨3 치고는 쉬운 것 같은데, 내가 너무 어렵게 접근한 것 같다

 

처음에는 '질문하기'를 보았는데 문과인 나는.. 도저히 해석하지를 못했다 ㅠㅅㅠ

대충.. 느낌상 말해보자면

1. 같은 숫자로 나눌 수 있으면 그것이 곱의 최대

2. 같은 숫자로 나눌 수 없으면 최대한 나눈 후 나머지 더해줌

 

인 것 같은데.. 아리까리 해서 다른 글을 찾아보았다

 

그렇게 보니, 대충 저 위의 설명이 이해가 가면서 ! 이렇게 풀어야 하는 이유가 이해가 됐다

우선, n으로 s를 나눈 몫이 일단 최대한 공평하게 나눈 것일테고!

그 값을 정답 배열에 넣고, n 중 하나의 숫자는 넣었으니 거기에서 -1 하고 

s에서 방금 들어간 원소를 빼고 위의 과정을 반복하면 또 최대한 공평하게 나눈 값이 나오고..

쭉쭉쭉쭉 하면 곱의 최댓값을 구할 수 있게 됨!

 

이과생들은 이거 금방 풀었을텐데.. 이럴 때 문과생은 서러버~..

2) 최종 소스코드

function solution(numbers) {
  let answer = 0;
  const done = [];
  const arr = [...numbers];
  const select = Array.from({ length: arr.length }, () => false);
  function prime(k) {
    if (done.includes(k) || k === 0 || k === 1) return;
    for (let i = 2; i * i <= k; i++) {
      if (k % i === 0) return;
    }
    answer++;
    done.push(k);
  }
  function dfs(count, n) {
    prime(Number(n));
    if (count >= arr.length) return;
    for (let i = 0; i < arr.length; i++) {
      if (select[i]) continue;
      select[i] = true;
      dfs(count + 1, n + arr[i]);
      select[i] = false;
    }
  }

  dfs(0, "");
  return answer;
}

3) 참고자료

https://yejin72.tistory.com/42

[프로그래머스 Level3] 최고의 집합 - 파이썬(Python)