57.수열 추측하기 - 순열, 이항계수

Updated:


🔍 문제

가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다.

그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다.

예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다

image

N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오.

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

🔹 입력설명

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

🔹 출력 설명

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

🔹 입력예제 1

4 16

🔹 출력 예제 1

3 1 2 4


📌 풀이

image

image

<head>
  <meta charset="UTF-8">
  <title>출력결과</title>
</head>

<body>
  <script>
    function solution(n, f) {
      let answer, flag = 0;
      let dy = Array.from(Array(11), () => Array(11).fill()); //  combi 함수 저장용 dy arr
      let ch = Array.from({length: n + 1}, () => 0); // check 용 배열
      let p = Array.from({length: n}, () => 0); // 순열 저장용 p arr
      let b = Array.from({length: n}, () => 0); // 조합된 숫자 보관용 b arr
      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));
  </script>
</body>

Leave a comment