[JavaScript/section 8] 13 - 수열 추측하기

📌 13 - 수열 추측하기

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

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

입력예제
4 16
출력예제
3 1 2 4

이번 문제를 풀기 위해서는 먼저 다음과 같은 규칙을 알아야한다.

빨간 색과 같이 순열의 첫 번째 부터 마지막 숫자까지 차례대로 n-1C0, n-1C1, n-1C2, n-1C3번 더해진 것을 알 수 있다. 결론적으로 순열 구하기와 조합의 경우 수 문제를 응용한 문제이다.

📝 풀이 방법

• 위 규칙에 따라 조합 수를 c 배열에 미리 저장한다.
• 재귀를 돌면서(순열을 구하는 과정) 숫자를 하나씩 선택할 때마다 sum에 p[L] * c[L]을 더해준다.
• L(레벨)과 n이 같고 sum(삼각형에서 가장 밑에 있는 숫자)과 f가 같다면 하나의 답이 완성된 것이므로 p 배열을 얕은 복사하여 answer에 할당해준다.
• 사전순으로 가장 앞에 오는 것을 출력해야하기 때문에 하나의 답이 완성되면 flag에 1을 할당하여 나머지를 모두 return한다.

function solution(n, f) {
  let answer,
    flag = 0;
  const dy = Array.from(Array(11), () => Array(11).fill(0));
  const ch = Array.from({ length: n + 1 }, () => 0);
  const p = Array.from({ length: n }, () => 0);
  const c = Array.from({ length: n }, () => 0);

  function combi(n, r) {
    if (dy[n][r] > 0) return dy[n][r];
    if (r === 0 || n === r) return 1;
    else return combi(n - 1, r - 1) + combi(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 (ch[i] === 0) {
          ch[i] = 1;
          p[L] = i;
          DFS(L + 1, sum + p[L] * c[L]);
          ch[i] = 0;
        }
      }
    }
  }

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

  DFS(0, 0);

  answer = answer.join(' ');
  return answer;
}

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