8-13. 수열 추측하기

문제

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

 

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

풀이

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

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

  function DFS(L, sum) {
    if (flag === 1) 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 + b[L] * p[L]);
          ch[i] = 0;
        }
      }
    }
  }

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

  return answer;
}

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

 

1. 규칙 각 순열마다 더하기를 중첩으로 하는 것이 아니라 각 순번마다 몇번 반복되는지 카운트해서 곱하기로 계산하는 식으로 했습니다.

 

3이 1개 1이 3개 2가 3개 4가 1개

이 숫자들은 조합의 규칙과 같습니다.

 

2. 따라서 순열을 구하고 b에 있는 배열과 곱하여서 원하는 숫자와 같다면 정답인 순열으로 하였습니다