처음에 그림 봤을 때부터 바로 조합이 떠올랐던 문제였지만,조건 중에 '다리끼리는 서로 겹쳐질 수 없다'고 해서 직접 그려봤다. M개에서 N개를 중복 없이 선택하는데, 여기서 다리가 교차되는 경우가 조금 헷갈렸다.그러나 해당 조건 하에 직접 그려서 세어본 결과 일반 조합의 계산결과와 동일했는데, 조합의 개념을 잘 생각해보면 쉽다. 조합은 순열과 달리 뽑는 순서 자체를 고려하지 않기 때문에 서쪽의 (1,2)가 각각 동쪽의 (1,4)를 선택하던 (4,1)을 선택하던 모두 하나의 경우의 수로 처리되게 된다.따라서 애초부터 다리가 교차되면 안된다는 조건은 조합 개념 자체에 포함되어 있는 것으로 판단할 수 있었다!즉, 서쪽이 N개, 동쪽이 M개이고 M개 중에 N개를 연결시키는 것이므로 조합으로 따지면 mCn을 계산..
