DFS - 수열 추측하기

문제

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

단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.

 

▣ 입력설명

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

 

▣ 출력설명

첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다.

답이 존재 하지 않는 경우는 입력으로 주어지지 않는다.

 

▣ 입력예제 1

4 16

 

▣ 출력예제 1

3 1 2 4

---

먼저 문제가 무엇을 요구하는지 파악하자.

N은 가장 윗줄에 있는 수의 갯수이고 F는 가장 밑에 있는 수이다.

N이 4로 주어질 때 맨 위에 있는 수열은 1 2 3 4 이며 이 수열로 파스칼 삼각형 연산을 했을 때 F를 만족하는 수열을 구해야한다. 즉, 순열을 구해야한다는 것이다.

그런데 매번 순열의 경우의 수마다 파스칼 연산을 하게되었을 때 최악의 경우를 고려해보자.

F는 최악의 경우 100만이다. 100만을 구하기위해 파스칼 연산을 하게되면 엄청나게 많은 연산이 소요된다. 그리고 N도 최대 10이므로 10! 마다 100만을 구하기위한 파스칼 연산을 하게된다면 ... 더이상 말은 생략한다.

 

규칙을 찾아보자.

그림과 같이 표현했더니 결국 가장 밑에 있는 수를 1*1 + 2*3 + 3*3 + 4*1 = 20 이렇게 구할 수 있다는 것을 알았다.

그리고 1 3 3 1 은 조합의 경우의 수로 표현할 수 있다. 단, n개중에 뽑는 경우가 아니라 n-1개 중에 뽑는 경우의 수이다.

참고로 위의 이항계수의 성질이 파스칼 삼각형과 연관이 있다.

 

지금까지의 과정을 정리해보자.

• 1부터 N까지의 수열을 순열을 이용해서 경우의 수를 구한다.
• 순열을 이용한 경우의 수들을 구했다면 각각의 수마다 n-1 combi 0, n-1 combi 1, ... n-1 combi n-1의 수를 곱해준다.
• 그리고 곱한 값이 K와 일치하다면 해당 수열이 정답이 된다.

---

코드

permutation 함수의 인자 l이 의미하는 것을 잘 생각해보자. l이 k라면 순열의 k+1번째 수가 결정되었다는 의미이다.

let [n, k] = require('fs').readFileSync('input.txt').toString().trim().split(' ').map(Number);
let dy = Array.from({ length: n + 4 }, () => Array.from({ length: n + 4 }).fill(0));
let ch = Array.from({ length: n + 1 }).fill(0);
let c = [];
let p = [];
let ret = 0;
let flag = 0;

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

function permutation(l, sum) {
  if (flag) return;
  if (l === n && sum === k) {
    ret = [...p];
    flag = 1;
    return;
  } else {
    for (let i = 1; i <= n; i++) {
      if (ch[i]) continue;
      ch[i] = 1;
      p.push(i);
      permutation(l + 1, sum + c[l] * p[l]);
      ch[i] = 0;
      p.pop();
    }
  }
}

function solution() {
  for (let i = 0; i < n; i++) c.push(combi(n - 1, i));
  permutation(0, 0);
  return ret;
}

console.log(solution());