[JS] 백준 1010: 다리 놓기

문제 요약

백준 1010번: 다리놓기

• 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다.
• 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다.
• 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.
• 서쪽 사이트 개수만큼(N개) 다리를 지으려고한다.
• 다리끼리는 서로 겹쳐질 수 없다.
• N, M (0 < N ≤ M < 30)

입력

3
2 2
1 5
13 29

출력

1
5
67863915

문제 분석

• 서쪽 사이트 개수만큼 다리를 지으려고 한 것이다.

• 동쪽 사이트는 서쪽 사이트 개수보다 크거나 같다.

• 한 사이트당 한개의 다리.
  → 조합! (n개 중에 r개 선택)

  $C(n,r)=C(n−1,r−1)+C(n−1,r)$
  현재 원소를 선택할 것인가? : $C(n−1,r−1)$
  현재 원소를 선택하지 않을 것인가?: $C(n−1,r)$

문제 설계

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const [t, ...arr] = input;

function solution(n, r) {
  let answer;
  let dy = Array.from(Array(30), () => Array(30).fill(0));

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

  answer = DFS(n, r);
  console.log(answer);
}
arr.forEach((i) => solution(+i.split(' ')[1], +i.split(' ')[0]));

이차원 배열 만들기 Array.from

• N, M (0 < N ≤ M < 30)이므로 그에 해당되는 이차원 배열을 만들어준다.
• dy[n][r]은 n개의 원소 중에서 r개를 선택하는 경우의 수 $C(n,r)$를 저장하는 것이다.

  let dy = Array.from(Array(30), () => Array(30).fill(0));

점화식을 이용해 조합 구현하기

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

  answer = DFS(n, r);

• if (dy[n][r] > 0) return dy[n][r]; 은 이미 계산된 값을 재사용하는 코드다.
• if (r === 0 || n === r) return 1; 은 아무것도 선택하지 않거나 전부를 선택했을 때 재귀를 멈추는 코드이다.
• else return (dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r));은 조합의 점화식을 이용하여 $C(n,r)=C(n−1,r−1)+C(n−1,r)$을 구현한 것이다.
• 결과를 answer에 저장한다.

출력 forEach

arr.forEach((i) => solution(+i.split(' ')[1], +i.split(' ')[0]));

• 기준을 동쪽(M개)에서 서쪽(N개)를 선택한 것으로 매개변수는 입력값 기준으로 바꿔서 넣어준다.