1010번 백준

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

1010번: 다리 놓기

from sys import stdin

for t in range(int(stdin.readline())):
    k, n = map(int, stdin.readline().split(' '))

    ans = 1
    for i in range(1, k+1):
        ans *= n-i+1
        ans //= i
    print(ans)

실생활에서 적용하여 설명하기 귀찮다 전단사 함수(일대일 함수) f(x)가 주어질 때, a < b 면 f(a) < f(b)를 만족하는 함수의 개수를 구하는 문제이다.

사실 이 문제를 보고 가장 먼저 생각이 난건 이거였다.

"아! 이거 고딩 때 확률과 통계 배울 때 나온 문제잖아!"

글쎄, 요즘은 확통을 선택과목으로 배운다고는 들었다. 라떼는 문과까지 확통이 필수였다고 ㅠ 그래도 대부분의 독자들은 경우의 수라는 개념을 너무 잊고 있을진 않을 것 같아서, 그냥 아는대로 설명해보려고 한다.

강 서쪽에 있는 입구들은 무조건 하나씩 다리를 놓아야 한다. 그럼 강 동쪽에 다리를 놓을 곳을 골라야 한다. 사진에서 보여준 예시를 예로 들면, 강 서쪽에는 4곳의 스팟이 있으니 강 동쪽에도 4곳의 스팟을 선택해야 된다는 것이다. 그럼 이제 4곳에 다리를 놓는다고 하면, 겹치지 않게 두기 위해서는 x자 없이 전부 일자로 놓는 경우 말고는 다른 선택지가 없을 것이다.

그렇다! 그렇게 놓을 곳을 정해두기만 하면, 다리를 놓는 경우의 수는 오직 한 가지라는 것이다! 따라서, 우리가 구해야 하는 경우의 수는, 강 동쪽에서 다리를 놓을 수 있는 경우의 수만 구하면 된다.

따라서, 강 서쪽의 스팟이 k곳, 강 동쪽의 스팟이 n곳이면, 경우의 수는 C(n, k)가 되니, 혹시 잘 모르겠다면 검색을 해보자!