[#1010] 다리놓기

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

1010번: 다리 놓기

 

문제에서 뭐가 필요한지
(경우가 필요한지/경우의 수가 필요한지) 잘 생각하고 풀자
무작정 쓰기 편한 함수만 쓰지 말고ㅠㅠ

 

 

 

처음 문제를 보고

mCn 으로 풀면 안되나? 틀은 이렇게 나올듯

from itertools import permutations

t = int(input())
for _ in range(t) : 
    n, m = map(int, input().split())
    m_list = list(range(1, m))
    print(len(list(permutations(m_list, n)))) # mPn 경우의 수

 

 

...^^ 나 .. 메모리초과 아티스트일지도 ?

 

 

다시 생각해봤을때

itertools가 편리한 도구이긴 하지만, 

모든 경우가 구체적으로 어떤 경우인지 알 필요가 없고, 경우의 '수'만 알면 된다. 

그러면 nCr = (n)! / (r)!(n-r)! 이니까 그냥 그대로 수학적으로 계산하면 된다.  

import math

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())
    print(math.factorial(m) // (math.factorial(n) * math.factorial(m - n))) # mCn 경우의 수

일케

 

 

 

하하 

문제에서 뭐가 필요한지
(경우가 필요한지/경우의 수가 필요한지) 잘 생각하고 풀자
무작정 쓰기 편한 함수만 쓰지 말고ㅠㅠ