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

정민경·2023년 1월 20일
0

baekjoon

목록 보기
22/57
post-thumbnail

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

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

- 입력 및 출력

[ 입력 ]

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

[ 출력 ]

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

- 문제 풀이

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

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

    • nCr

      ex) 5C3 = 5x4x3 / 3x2x1

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

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

- 최종 코드

0개의 댓글