수열 추측하기 - Node.js

수열 추측하기

---

문제

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

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

입력

첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의 미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.

출력

첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다. 답이 존재 하지 않는 경우는 입력으로 주어지지 않는다.

입력 예시 1

4 16

출력 예시 1

3 1 2 4

---

해결방법

function solution(N, F) {
  let answer;
  let dynamic_array = Array.from(Array(11), () => Array(11).fill(0));
  let channel = Array.from({ length: N + 1 }, () => 0);
  let p = Array.from({ length: N }, () => 0);
  let b = Array.from({ length: N }, () => 0);
  let flag = 0;
  function combination(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] =
        combination(N - 1, R - 1) + combination(N - 1, R));
    }
  }
  function DFS(L, sum) {
    if (flag) {
      return;
    }
    if (L === N && sum === F) {
      answer = p.slice();
      flag = 1;
    } else {
      for (let i = 1; i <= N; i++) {
        if (channel[i] === 0) {
          channel[i] = 1;
          p[L] = i;
          DFS(L + 1, sum + b[L] * p[L]);
          channel[i] = 0;
        }
      }
    }
  }
  for (let i = 0; i < N; i++) {
    b[i] = combination(N - 1, i);
  }
  DFS(0, 0);
  return answer;
}

console.log(solution(4, 16));

---