수열 추측하기

문제

 

문제풀이

먼저 해당 문제를 풀기 위해서는 파스칼의 삼각형을 실행한 결과값이 이항계수를 이용해 계산한 최종값과 같음을 알아야 한다.

 

파스칼의 삼각형과 이항 계수 원리

다음 그림에서 본 바와 같이 파스칼의 삼각형을 실행한 결과 값은 (1 × 1) + (2 × 3) + (3 × 3) + (4 × 1)이며 N이 4일 경우에 수열 순서가 어떻든 간에 {1 3 3 1}의 범위 내에서 결과값이 산출된다.

 

또한 이를 좀 더 구하기 편한 이항 계수로 표현한다면 3C0 3C1 3C2 3C3로 바꿀 수 있다.

 

{1 3 3 1}을 이항 계수로 구해두지 않을 경우 순열을 구할 때마다 매번 파스칼의 삼각형 과정을 거쳐야 하는데 이는 시간 복잡도 상 매우 비효율적이다.

 

코드

function solution(n, f) {
  let answer = [];
  let flag = 0;
  let dy = Array.from(Array(11), () => Array(30).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];
    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) 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])); //{1, 3, 3, 1} * {1, 2, 3, 4}, {2, 1, 3, 4} ...
          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));