백준) 1010 - 다리 놓기

📌 문제 링크

https://www.acmicpc.net/problem/1010

---

📌 문제 탐색하기

• 다리를 놓으려 할 때 강 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다.(N ≤ M)
• 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 할 때, 최대 한 개의 다리만 연결될 수 있다.
• 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

시간복잡도

• O(n^2)

알고리즘 선택

• DP

---

📌 코드 설계하기

1. 문제의 input을 개행으로 분리해서 가져온 뒤, 띄어쓰기로 분리하여 숫자로 변환합니다.
2. `dp` 배열을 생성하고 `0`으로 초기화합니다.
3. 기본 경우를 설정합니다.

• 서쪽과 동쪽 사이트가 없을 때
• 서쪽 사이트가 존재하나 동쪽 사이트가 없을 때
• 서쪽 사이트가 없으나 동쪽 사이트가 있을 때

  4. dp 배열을 채웁니다.

• `i`: 동쪽 사이트의 총 개수
• `j`: 서쪽 사이트의 총 개수
• `dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]`: 이전 행의 두 값을 더하여 현재 값을 계산합니다. 

5. 값을 출력합니다.

---

📌 정답 코드

//https://www.acmicpc.net/problem/1010
export {};

const fs = require("fs");
const filePath =
  process.platform === "linux" ? "/dev/stdin" : __dirname + "/input1.txt";
const [_, ...input] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n")
  .map((x: string) => x.split(" ").map(Number));

const bridge = (k: number, n: number) => {
  const dp = Array.from(Array(n + 1), () => new Array(n + 1).fill(0));

  dp[0][0] = 1;
  dp[1][0] = 1;
  dp[1][1] = 1;

  for (let i = 2; i <= n; i++) {
    for (let j = 0; j <= i; j++) {
      if (j === 0 || j === i) {
        dp[i][j] = 1;
      } else {
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
      }
    }
  }
  console.log(dp[n][k]);
};

input.forEach((y: number[]) => bridge(y[0], y[1]));