[C/C++] 백준 #1010 다리 놓기(조합)

백준 #1010 다리 놓기 문제는 수학 중 확통의 경우의 수에 어느정도 개념이 있어야 풀 수 있는 문제입니다.

 

constructing bridges

 

강을 사이로 왼쪽에는 N 개의 지역, 오른쪽에는 M 개의 지역이 있습니다.  이 N개의 지역에 하나씩 다리를 놓아서 오른쪽에 있는 M개의 지역을 연결하고자 하는데, 다리가 서로 엇갈리지 않도록 하는 경우의 수를 물어보고 있습니다.

 

다리 놓기

 

경우의 수를 따지는 데에는 순열과 조합이 있는데, 이와 같이 엇갈리지 않게, 즉, 항상 정해진 순서대로(또는 증가하는 순서, 감소하는 순서 등) 나열해야한다면, 이것은 조합을 선택해야 합니다.  결국 이 문제는 M개 중에서 N개를 선택하는 문제가 되겠죠.

 

실제 백준 문제는 다음 링크를 봐주세요.

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

1010번: 다리 놓기

 

백준 문제를 풀 때, 숫자의 범위를 늘 생각해야 하는데, int 형으로 풀 수 있는지 아닌지.  그리고 연산하는 중간에 숫자의 범위가 벗어나는지 아닌지 등을 고려해야 합니다.  사실 일일이 따져서 프로그램하는 것이 귀찮기 때문에, 좀 미심쩍다 싶으면, 넓은 범위의 자료형을 쓰곤 합니다. 

 

조합을 계산하기 위해서는 연속된 숫자의 곱을 사용하게 되는데, 여기서 오버플로우가 생길 수 있습니다.  그럴 때에는 최종 답이 int형이 되더라도 long long으로 바꾸어 주는게 필요할 수 있습니다.

 

제가 이번에 사용한 조합 계산 알고리즘은 단순하게 for 루프를 이용했습니다.  이 경우라면, 중간 과정에서 오버플로우가 생길 가능성이 농후해집니다.  (다른 방식의 조합 계산 알고리즘을 쓰면 해결할 수도 있습니다.)  특히 숫자 범위가 조합에서 30까지 간다면, 100%로 int 형으로는 오버플로우가 생깁니다.  10! 이 \(10^6\) 정도이니까요.  int 형이 감당할 수 있는 수의 범위는 13! 정도입니다.  long long 으로 감당할 수 있는 숫자 범위는 \(10^{18}\) 정도이니까, 대략 24! 정도까지는 될 듯 하네요.  30까지 갈 경우 사실 long long 으로도 생각해보아야 하겠지만, 실제 30개의 수를 다 곱해서 팩토리얼 계산할 것은 아니니까.

 

그래서 나온 소스는 다음과 같습니다.  소스는 참고용으로만 봐주세요.

 

//----------------------------------------------------------------------------------------
//  baekjoon #1010
//    - by Aubrey Choi
//    - created at 2019-08-02
//----------------------------------------------------------------------------------------
#include <stdio.h>

long long comb(int n, int k)
{
  long long c=1;
  if(2*k > n) k=n-k;
  for(int i=1; i<=k; i++)
    c = c*(n--)/i;
  return c;
}

int main()
{
  int t, n, m;
  scanf("%d", &t);
  while(t--)
  {
    scanf("%d%d", &n, &m);
    printf("%lld\n", comb(m,n));
  }
  return 0;
}