백준 1010: 다리놓기 (Python, 조합, math.comb())

 

요새 알고리즘을 하는둥 마는둥 깔짝이다

저번 주에 오오오오랜만에 코테를 무려 4개나 치루고,, 많은 자극을 받았다.

 

기본 문제부터 다시 차근차근 풀어볼 예정으로 오랜만에 백준으로 문풀을 했다.

 

 

문제 : 다리놓기

1010번: 다리 놓기

 

 

 

< 그림과 같이 강 동쪽(M)에서 강 서쪽(N)으로 겹치지 않게 다리를

놓을 수 있는 경우의 가지수를 출력하면 된다 ~_~

조합문제여서 python combinations를 사용해서 쓰면 (N=13, M=29)만 되어도

실행시간이 엄청 오래걸리고 제출 시 런타임에러가 발생한다.

 

문제에서 의도한 바는 조합 공식 (m!/n!(m-n)!) 을 활용해 푸는 거인 것 같지만,,

파이썬에는 조합의 개수를 바로 구해주는 math 함수가 있다. (개꿀)

 

 

 

 

풀이

import math

if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        N,M = map(int,input().split()) # mCn
        arr = list(range(1,M+1))

        #print(len(list(it.combinations(arr,N)))) #Runtime ERR
        print(math.comb(M,N))

 

math.comb(M,N)를 사용하면 M개에서 N개를 조합으로 선택할 때의 경우의 수를 출력한다.