[C++] 백준 1010번 풀이 (다리 놓기)

- 문제 (1010번) : 다리 놓기

• 링크 : https://www.acmicpc.net/problem/1010

• 강을 사이에 두고 왼쪽과 오른쪽의 사이트의 개수을 알 때 서로 겹치지 않는 다리를 지을 수 있는 경우의 수를 구하는 문제

---

- 입력 및 출력

[ 입력 ]

• 첫번째 줄에 테스트케이스 개수 T 입력
• 두번째줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수(N, M) 입력
  ( 0 ＜ N ≤ M ＜ 30 )

[ 출력 ]

• 각 테스트케이스에 대해 다리를 지을 수 있는 경우의 수 출력

---

- 문제 풀이

• 이 문제는 간단한 이항정리 문제이다.

  이항정리 <- combination ( 조합 ) 으로 접근

  • ｎCｒ

    ex) 5C3 = 5x4x3 / 3x2x1

• combination을 사용할 때 숫자의 순서에 주의한다.

  • 동쪽 사이트의 개수 중 서쪽 사이트의 개수를 선택하는 것이므로
    • 서쪽 사이트 : n, 동쪽 사이트 : m 이라 했을 때
      ｎCｍ 이 된다.

---

- 최종 코드