✓

태그:

16. 정수론 및 조합론

강동의 사이트를 강서의 사이트 개수만큼 고르는 경우랑 같지 않을까요…??

풀이 비스무리한거 보기

강을 기준으로 양쪽에 사이트가 있을 때, 이 사이트를 연결하여 최대로 다리를 짓는 경우의 수를 구하는 문제입니다. 문제의 조건에서 강서의 사이트는 강동보다 항상 작거나 같으므로 강서의 사이트는 항상 모두 사용합니다. 따라서 다리는 항상 강서의 사이트 개수만큼 짓게 됩니다. 그러면 이제 강동의 사이트를 연결하는 경우의 수를 구해야되는데, 문제의 조건에서 다리끼리 겹칠 수는 없다고 했기 때문에 목표로 하는 경우의 수는 강동의 사이트 중에서 강서의 사이트 개수만큼 뽑는 경우가 됩니다. 뽑는 각 경우에 대해 강서의 사이트와 연결되는 경우는 오직 한 가지만 나오기 떄문입니다. 따라서 강서의 사이트를 n, 강동의 사이트를 m이라고 하면 _mC_n를 구하면 됩니다.

소스 코드

언어	코드	시간	비고
Python 3	코드(Github) / 코드(백준)	2021-01-10 14:11:32

---