조합의 경우의 수(메모이제이션)

조합의 경우의 수(메모이제이션)

---

문제

입력

첫째 줄에 자연수 n(3<=n<=33)과 r(0<=r<=n)이 입력됩니다.

출력

첫째 줄에 조합수를 출력합니다.

입력 예시 1

5 3

출력 예시 1

10

입력 예시 2

33 19

출력 예시 2

818809200

---

해결방법

function solution(N, R) {
  let answer;
  function DFS(N, R) {
    if (N === R || R === 0) {
      return 1;
    } else {
      return DFS(N - 1, R - 1) + DFS(N - 1, R);
    }
  }
  answer = DFS(N, R);
  return answer;
}

console.log(solution(5, 3));

// 메모이제이션 적용
function solution2(N, R) {
  let answer;
  let dynamic_array = Array.from(Array(35), () => Array(35).fill(0));

  function DFS(N, R) {
    if (dynamic_array[N][R] > 0) {
      return dynamic_array[N][R];
    }
    if (N === R || R === 0) {
      return 1;
    } else {
      return (dynamic_array[N][R] = DFS(N - 1, R - 1) + DFS(N - 1, R));
    }
  }
  answer = DFS(N, R);
  return answer;
}

console.log(solution2(33, 19));

---