[코딩테스트] 수열 추측하기, 순열 & 이항계수 응용

1. 문제 

가장 윗줄에 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) 문제해석

 

1 2 3 4 라는 값이 맨 윗 줄에 있다고 생각해보자.

해당 값을 파스칼의 삼각형처럼 위의 두 개 값을 더해보면 아래와 같이 나온다.

 

1 2 3 4를 파스칼의 삼각형으로 구현하면, 맨 마지막 값은 1+2+2+2+3+3+3+4와 같다.

이를 좀 더 보기 편하게 곱으로 바꿔보면, 1*1 + 2*3 + 3*3 + 4*1이  된다.

 

4개의 숫자를 이용해 파스칼의 삼각형을 구한다면, 위에서 구한 값과 똑같이 항상 1 3 3 1이 나온다. 

따라서 n이 4라면, 각 자리수에 있는 숫자를 1 3 3 1로 곱해주면 된다.

 

만일 3 1 2 4로 파스칼의 삼각형을 구현한다고 생각해보자.

그럼 3*1 + 1*3 + 2*3 + 4*1을 하면 된다. 

 

그리고 이 1 3 3 1을 조합으로 표시하면, 3C0 3C1 3C2 3C3와 같다. 

만일 숫자가 5개라고 하면, 4C0 4C1 4C2 4C3 4C4와 같게 된다.

따라서 해당 값은 1 4 6 4 1이 되고, 여기에 1 2 3 4 5를 곱해주면 된다. 

 

 

2. 문제 해결

function solution(n, f) {
    let answer;
    let flag = 0;  //순열 확인
    let dy = Array.from(Array(11), () => Array(11).fill(0));  //조합수 메모이제이션
    let b = Array.from({ length: n }, () => 0);  //미리 조합수 구하기
    let ch = Array.from({ length: n + 1 }, () => 0);  //체크배열
    let p = 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]));
                    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));

 

위에서 생각했던 공식을 떠올려서, 우선 1 3 3 1의 값을 구해줘야 한다.

1 3 3 1 값을 넣은 배열을 만들고, 1 2 3 4로 조합한 4개의 숫자를 배열의 값과 곱해서 주어진 숫자와 같은지 확인해보면 된다. 

 

 

let dy = Array.from(Array(11), () => Array(11).fill(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);
}
 
//조합수 구하기 호출
for (let i = 0; i < n; i++) {
  b[i] = combi(n - 1, i);
}

 

우선, 1 3 3 1의 값을 구하기 위해 조합수를 구하는 함수 combi를 만들어준다.

조합수에 관련된 내용은 이전 포스팅에 자세히 설명되어 있다.

 

n개의 조합수를 구해야 하기 때문에 for문을 이용해 combi 함수를 호출해준다.

그리고 해당 조합수의 값을 b라는 배열에 저장해준다.

 

 

let answer;
let flag = 0;  //순열 확인
let ch = Array.from({ length: n + 1 }, () => 0);  //체크배열
let p = Array.from({ length: n }, () => 0);  //순열저장
    
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]));
        ch[i] = 0;
      }
    }
  }
}

DFS(0, 0)

 

이제 DFS 함수를 만들어보자.

1부터 n까지의 순열을 구한 후, 각각의 순열 * 조합수를 모두 더한 값이 주어진 f와 같은지 비교해주면 된다.

 

ch라는 체크배열을 만들고, p안에 순열 값을 저장해준다. 

그리고 L===n(n개를 모두 체크함)이거나 sum===f라면 p의 값을 answer에 넣어준다.

순열 구하는 방법도 이전 포스팅에 자세히 설명되어 있다.

 

그리고 flag 변수를 만들어, 값이 구해지면 더이상 DFS가 실행되지 않도록 해준다.