👨‍💻 사건

1~N 까지의 수를

1  2  3  4
  3  5  7
	 8  12
		20

위 와 같은 형태로 그려나간다고 할때, 가장 아래의 숫자 F 와 1~N 의 N 을 주어질때 가장 첫단 (예시로는 1234) 을 예측하는 문제를 풀어보았다.

처음에는 1~N까지의 순열을 저장하여, 각각 전부 파스칼 삼각형의 형태로 위와 같이 계산해 내려간후 F와 맞는것을 찾고자 하였다. 그렇게 된다면, 너무 시간복잡도가 높아지기때문에 이항계수를 사용하여 문제를 풀어보았다.

✅ 해결

일단 이문제는 이항계수를 활용하면, 첫단의 줄만 알수있으면 바로 합계를 구할수있다.

위의 사진처럼 N에 따라 각 첫단의 배열의 개수는

$(N-1)C0$,$(N-1)C1$,…,$(N-1)C(N-1)$

이 된다.

그럼 첫단이 주어질때 합계는
Arr[0]$(N-1)C0$+Arr[1]$(N-1)C1$+…+Arr[N-1]*$(N-1)C(N-1)$ 이 된다.

이를 활용하여 문제를 해결해 나갔다.

function solution(n, f) {
  let answer = [];
  let firstArrayFlag = 0;
  let dy = Array.from(Array(11), () => Array(11).fill(0));
  let visited = Array.from({ length: n + 1 }, (v) => 0);
  let numArr = Array.from({ length: n }, (v) => 0);
  let calNumArr = Array.from({ length: n }, (v) => 0);
  function combination(n, r) {
    if (dy[n][r] > 0) return dy[n][r];
    if (r === 0 || n === r) {
      return 1;
    } else {
      return (dy[n][r] = combination(n - 1, r - 1) + combination(n - 1, r));
    }
  }
  for (let i = 0; i < n; i++) {
    calNumArr[i] = combination(n - 1, i);
  }
  function DFS(level, sum) {
    if (firstArrayFlag) {
      return;
    }
    if (level === n && sum === f) {
      answer = [...numArr];
      firstArrayFlag = 1;
    } else {
      for (let i = 1; i <= n; i++) {
        if (visited[i] === 0) {
          visited[i] = 1;
          numArr[level] = i;
          DFS(level + 1, sum + calNumArr[level] * numArr[level]);
          visited[i] = 0;
        }
      }
    }
  }
  DFS(0, 0);
  return answer;
}
console.log(solution(4, 16));