스크린샷 2023-03-14 170903.png

문제

1010번: 다리 놓기


조건

  1. 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다. (N ≤ M)

  2. N개의 다리를 지어야 한다.

  3. 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.

    1. 한 사이트는 한번만 선택 가능하다는 의미 → 즉, 중복이 불가능하다.
  4. 다리끼리는 서로 겹쳐질 수 없다.

    IMG_B23F3AB40FA1-1.jpeg


접근법

  1. M개의 사이트 중 N개의 사이트를 뽑는 느낌 → 조합

  2. 조합만하면 느낌상 뭔가 교차되는 다리는 고려안하는 느낌인데..

  3. 조합은 아래의 경우가 모두 하나의 동일한 경우의 수이다. (순서는 고려하지 않으므로)

    IMG_0C456A24ED54-1.jpeg