1. 수열 예측

이번엔 수열을 예측한다. 숫자들이 나열되어있는데 각각 더하다 보면 최종적인 합이 나온다 그 합을 보고 맨처음 시작된 수열을 예측하는 함수를 만드는것이다. 아래 예시를 살펴보자.

예를들어 [3,1,2,4] 라는 수열이 있다. 이 수열을 더해나가 보자
3  1  2  4
  4  3  6
   7  9
    16

그래서 16을 통해서 3,1,2,4 를 뽑아내면 된거다.

그럼 어떻게 시작해야할까? 사실 전혀 감이 오지 않는다. 이전에 만든 조합과 어떤 관계가 있는 것일까?
이때는 좀 독특한 방법이 있다.

  3     1     2     4
    3+1   1+2   2+4
    3+1+1+2 1+2+2+4
    3+1+1+2+1+2+2+4

=> 3*1 + 1*2 + 2*3 + 4*1

이걸 조합으로 나타내면 3*3C0 + 1*3C1 + 2*3C2 + 4*3C3 로 나타낼 수 있다. 그럼4이하의 숫자의 경우를 구하고 각각의 숫자에 오름차순 조합을 곱해서 더한 값이 16이 되면 되는거다.

그럼 코드를 짜보자!

2. 접근 방법

• pseudoCode
  • ch 배열을 만들어서 수의 조합을 체크한다
  • p를 만들어서 ch에 따라서 수의 조합을 만든다.
  • 이전시간에 만든 함수를 이용해서 조합과 p를 곱하고 sum으로 넘긴다.
  • level 이 같고 sum이 같으면 된다.
    • found = true로 해서 cut edge한다

function combGuessing(n, finalSum) {
  let ch = Array.from({ length: n + 1 }, () => 0);
  let p = [];
  let answer;

  let combPackage = {};

  let found = false;

  function dfs(level, sum) {
    if (found) return;
    if (level === n && sum === finalSum) {
      answer = p.slice();
      found = true;
    } else {
      for (let i = 1; i <= n; i++) {
        if (ch[i] === 0) {
          ch[i] = 1;
          p[level] = i;
          dfs(level + 1, sum + combPackage[`${n - 1}C${level}`] * p[level]);
          ch[i] = 0;
        }
      }
    }
  }

  // 필요한 조합을 저장함
  for (let i = 0; i < n; i++) {
    combPackage[`${n - 1}C${i}`] = combinationCases(n - 1, i);
  }

  dfs(0, 0);
}

배웠던걸 써먹자! 이전에 배웠던 cut edge/ch배열/조합 함수 를 모두 써먹은 문제였다. 써먹으니 맛있잖아?