[알고리즘/인프런] 수열 추측하기(순열, 이항계수)

문제 

---

가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼
의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이그려진다.

 

3 1 2 4
4 3 6
7 9
16

 

N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.

 

풀이

---

#1

function countCombs(n, r) {
  let memo = Array.from({ length: n + 1 }, () =>
    Array.from({ length: r + 1 }, () => 0)
  );

  function DFS(n, r) {
    if (r === 0 || n === r) return 1;
    if (memo[n][r]) return memo[n][r];
    else {
      return (memo[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r));
    }
  }

  return DFS(n, r);
}

function solution(n, f) {
  const comb = Array.from({ length: n }, (val, idx) => countCombs(n - 1, idx));
  let ch = Array.from({ length: n }, () => 0);
  let picked = Array.from({ length: n }, () => 0);
  let answer = [];
  let flag = 0;

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

    if (L === n) {
      const result = comb.reduce((acc, cur, idx) => acc + cur * picked[idx], 0);

      if (result === f) {
        answer = [...picked];
        flag = 1;
      }
    } else {
      for (let i = 0; i < n; i++) {
        if (ch[i] === 0) {
          ch[i] = 1;
          picked[L] = i + 1;

          DFS(L + 1);
          ch[i] = 0;
        }
      }
    }
  }

  DFS(0);
  return answer;
}

처음에는 1~N까지 수에서 N개를 뽑는 순열을 구하고 그 수를 각각 더했을 때 결과값 F가 나올 경우를 찾아내면 된다고 생각했다. 하지만 이 풀이는 시간이 너무 오래 걸리기 때문에 이항계수를 활용해 풀어야했다.

 1         2        3       4
 
     1+2       2+3    3+4
     
       1+2+2+3    2+3+3+4
       
         1+2+2+2+3+3+3+4

모든 값이 더해진 마지막 식을 보면 1 x 3C0 + 2 x 3C1 + 3 x 3C2 + 4 x 3C3와 같음을 알 수 있다. 따라서 각 숫자에 n-1Cr을 곱해준 값을 모두 더하면 가장 마지막 줄의 값을 구할 수 있다.

 

---

 

#2

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

위와 같이 재귀를 돌 때 순열(p)과 조합(c) 배열의 인덱스 L 값을 가져와 전달해주면 매번 L===r일 때 reduce로 연산하지 않아도 된다.