Algorithm JS - 수열 추측하기

jiny·2023년 1월 21일
0

JavaScript Algorithm

목록 보기
17/23
post-thumbnail

문제

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

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

입력 설명

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

4 16

출력 설명

첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다. 답이 존재 하지 않는 경우는 입력으로 주어지지 않는다.

3 1 2 4

풀이

파스칼의 삼각형은 이렇게 순열에 대해 각 순열의 값을 더해가며 최종적으로 가장 밑의 수는 1+2+2+2+3+3+3+4의 형태가 된다.

하지만 1~n까지 순열의 경우의 수는 n! 이다. 만약 n이 커지면 커질 수록 시간 복잡도가 증가하여 연산에 오랜 시간이 걸릴 것이다.

모든 순열을 파스칼의 삼각형에 대입하는 것이 아닌 이항 정리를 고려해 볼 수도 있다. 결국 16이라는 숫자는 1를 1번, 2와 3을 3번, 4를 1번 곱한 후 더한 값이기 때문이다.

즉, 파스칼 삼각형의 가장 위 층의 숫자들을 각각 이항 정리의 자릿수와 곱한 후 더하면(1 x 3 + 3 x 1 + 3 x 2 + 1 x 4) 파스칼 삼각형의 가장 밑의 수와 동일한 결과 값을 얻어 낼 수 있다.

전체적인 알고리즘의 흐름은 다음과 같다.

  1. n에 대한 이항 계수를 구한다.
  2. 순열을 만들어가며 (순열의 각 자리수 * 조합 수의 각 자리수) 들을 각각 더한 후 파스칼 삼각형의 최종 값과 비교한다.
  3. 만약 같다면 그 순열을 반환한다.
  4. 아니라면 다른 순열을 만든 후 2의 과정을 반복하여 3을 도출해낸다.

function solution(n, f) {
  
  // answer와 flag(순열이 answer에 들어갈 경우 종료 하기 위함)
  let answer,
    flag = 0;
  // 조합 수에 대해 메모이제이션 하기 위한 dy
  let dy = Array.from(Array(n + 1), () => Array(n + 1).fill(0));
  // 순열 생성을 위한 check 배열
  let ch = Array.from({ length: n + 1 }, () => 0);
  // 순열 p
  let p = Array.from({ length: n }, () => 0);
  // 조합 수 b
  let b = Array.from({ length: n }, () => 0);
  
  // combination 함수를 통해 조합수를 도출
  function combination(n, r) {
    if (dy[n][r] > 0) return dy[n][r];
    if (n === r || r === 0) return 1;
    else return (dy[n][r] = combination(n - 1, r - 1) + combination(n - 1, r));
  }
  
  // answer를 도출해내기 위한 DFS 함수
  function DFS(l, sum) {
    // 만약 flag === 1이면 순열이 answer에 들어갔기 때문에 종료
    if (flag) return;
    // 만약 순열이 만들어졌고 순열의 각 자리수 * 조합 수의 각 자리수를
    // 각각 더한 값이 f(가장 밑의 줄의 수)와 같다면 answer에 추가 후 flag = 1
    if (l === n && sum === f) {
      answer = p.slice();
      flag = 1;
      // 순열을 생성해가며 기존 sum에서 순열의 각 자리수와 조합 수의 각 자리수를 곱해서 더함
    } else {
      for (let i = 1; i <= n; i++) {
        if (ch[i] === 0) {
          ch[i] = 1;
          p[l] = i;
          DFS(l + 1, sum + p[l] * b[l]);
          ch[i] = 0;
        }
      }
    }
  }
  
  // 조합 수를 b에 추가
  for (let i = 0; i < n; i++) {
    b[i] = combination(n - 1, i);
  }
  DFS(0, 0);
  return answer;
}

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

0개의 댓글