[백준/Python] 1010번 : 다리 놓기

 

 

 

처음에 그림 봤을 때부터 바로 조합이 떠올랐던 문제였지만,

조건 중에 '다리끼리는 서로 겹쳐질 수 없다'고 해서 직접 그려봤다.

 

M개에서 N개를 중복 없이 선택하는데, 여기서 다리가 교차되는 경우가 조금 헷갈렸다.

그러나 해당 조건 하에 직접 그려서 세어본 결과 일반 조합의 계산결과와 동일했는데, 조합의 개념을 잘 생각해보면 쉽다.
조합은 순열과 달리 뽑는 순서 자체를 고려하지 않기 때문에 서쪽의 (1,2)가 각각 동쪽의 (1,4)를 선택하던 (4,1)을 선택하던 모두 하나의 경우의 수로 처리되게 된다.

따라서 애초부터 다리가 교차되면 안된다는 조건은 조합 개념 자체에 포함되어 있는 것으로 판단할 수 있었다!

즉, 서쪽이 N개, 동쪽이 M개이고 M개 중에 N개를 연결시키는 것이므로 조합으로 따지면 mCn을 계산하면 되겠다.

 

T = int(input())
lst = []
for _ in range(T):
    N, M = map(int, input().split())
    num = 1
    for i in range(N):
        num *= (M-i)
        num //= (i+1)
    lst.append(int(num))

for result in lst:
    print(result)

 

T개의 테스트 케이스에 대해서 각각 N과 M을 먼저 입력받는다.

그 후 바로 num 변수를 1로 초기화하여 생성하고, N번 만큼 반복하는 for문을 더 작성하여 여기서 조합을 계산한다.

앞서 봤던 조합 공식에서 n! 과 (n-r)!을 약분한 값을 num에 곱하기 위해 (M-i)를 매 회마다 곱해주고, r!를 나눠주기 위해 (i+1)을 num에서 나눈다.

 

예를 들어 4C2를 계산한다고 할 때, M = 4, N = 2 이므로

i=0 번째일 때 => num = 4 // 1 = 4

i=1 번째 일 때 => num = (4 * 3) // (1 * 2) = 6 가 되어 결과가 6이 되는 원리이다.

 

이를 예시 출력처럼 한 번에 출력하기 위해 각 테스트케이스의 결과를 리스트에 쌓아두고, 마지막에 for문으로 result를 출력해주면 종료한다.

 

처음에 num에서 (i+1)을 / 로만 나눠서 틀렸었는데, 부동소수점을 고려하지 않아 // 로 바꿨더니 맞았다.