[백준] 1010 다리 놓기

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

이 문제를 자세히 해석해보면, 조합의 문제이다.
즉 nCr을 구하라는 것이다.

잠시 조합과 순열을 설명하자면, 순열은 nPr 이라 하고 조합은 nCr 이라고 한다.
순열의 식은 n!/(n-r)! 이고 조합은 nPr/r! 이다. 
순열은 n개중 r개를 중복이 불가능하게 뽑는 것이고, 조합은 n개중 r개를 중복이 가능하게 뽑는 것이다.

즉, 이 문제는 다리끼리는 겹칠 수 없고 양쪽의 장소를 연결하는 것 이기 때문에 조합을 구하면 되는 간단한 문제이다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include <stdio.h>   int arr[100]={0};   int pp(int a,int b) {     int i;     arr[0]=a;     if(a==b)         return 1;          for(i=1;i<=b;i++)     {         arr[i]=arr[i-1]*(a-i)/(i+1);         //printf("%d\n",arr[i]);     }     return arr[i-2]; }     int main() {     int num,Left,Right,temp;     scanf("%d",&num);     for(int i=0;i<num;i++)     {         scanf("%d %d",&Left,&Right);         if(Left<Right)         {             temp=Right;             Right=Left;             Left=temp;         }         printf("%d\n",pp(Left,Right));      }  } Colored by Color Scripter

cs

dp를 이용해 pp 함수의 배열 맨 왼쪽부터 오른쪽으로 나누면서 채워나가는 식으로 코드를 짰다.