수열 추측하기

코드

  function solution(n, f) {
    let answer,
      flag = 0;

    let dy = Array.from(Array(11), () => Array(11).fill(0));
    let ary = Array.from({ length: n }, () => 0);
    let b = Array.from({ length: n }, () => 0);
    let ch = Array.from({ length: n + 1 }, () => 0);

    function comb(n, r) {
      if (dy[n][r] > 0) return dy[n][r];

      if (n === r || r === 0) {
        return 1;
      } else {
        return (dy[n][r] = comb(n - 1, r - 1) + comb(n - 1, r));
      }
    }

    function DFS(L, sum) {
      if (flag) return;

      if (sum === f && L === n) {
        answer = ary.slice();
        flag = 1;
      } else {
        for (let i = 1; i <= n; i++) {
          if (ch[i] === 0) {
            ch[i] = 1;
            ary[L] = i;
            DFS(L + 1, sum + ary[L] * b[L]);
            ch[i] = 0;
          }
        }
      }
    }

    for (let i = 0; i < n; i++) {
      b[i] = comb(n - 1, i);
    }

    DFS(0, 0);

    return answer;
  }

해결 방법

이 문제의 파스칼 삼격형을 보면 이런 풀이가 나온다. 

풀이를 자세히보면 각 자연수 뒤에 곱해주는 값이 3C0, 3C1, 3C2, 3C3이다. 따라서 조합을 이용해서 풀어주면 된다.

변수

answer: 정답 저장하는 변수

flag: 답을 구했으면 더 이상 스택에 쌓인 함수들을 실행할 필요가 없음을 알려는 변수

dy: comb 함수에서 값을 메모이제이션하는 배열

ary: 1부터 N까지 숫자를 저장하는 배열

b: (N-1)C(r)의 값을 저장하는 배열

ch: 1부터 N까지 숫자의 사용 여부를 체크하는 배열

comb(n, r)

https://shortcoding.tistory.com/420

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

comb 함수는 위 글을 참고해서 사용하면 될 것이다.

DFS(L, sum)

우선 flag가 1이되면 모든 함수 실행을 중지하도록 구현하였다.

 

만약 L===n이고 sum===f이면 answer에 ary를 깊은 복사를 하여 줬고 flag를 1로 만들어 더 이상 실행하지 않도록 했다.

위 경우가 아닌 경우 for문을 이용하여 ary의 모든 경우의 수를 구하는 코드를 작성했다. 먼저 ary[0]이 1인 경우를 모두 다 구하고 ary[0]이 2인 경우를 구하는 식으로해야 하기 때문에 이미 사용한 ch[i]를 0으로 바꿔줘야한다.

for문

for (let i = 0; i < n; i++) {
  b[i] = comb(n - 1, i);
}

이 for문에서는 (n-1)C(0), (n-1)C(1), ... , (n-1)C(n-1)을 구해서 b에 저장한다.