[백준_python] 다리 놓기 || 1010 ( 조합 )

1010번: 다리 놓기 (acmicpc.net)

1010번: 다리 놓기

이전 풀이

2021.02.05 - [문제 풀이/PYTHON] - [백준_python] 다리 놓기 || 1010

[백준_python] 다리 놓기 || 1010

n이 서쪽, m이 동쪽. m에서 겹치지 않게 n만큼을 뽑아주면 된다. 
예제를 함께 보면, 2C2, 5C1, 29C13이 결과값이 된다.
 
파이썬에는 조합을 편리하게 할 수 있도록 combination을 이용할 수 있다.
permutation도 존재한다.

 

from itertools import combinations

를 추가해주면 combinations(arr, n)으로 사용 가능하다. arr이라는 리스트들의 값 중에서 n개씩 뽑아 조합해준다.

 

from itertools import combinations

t = int(input())
for _ in range(t):
    n, m = map(int, input().split(' '))
    arr = [0] * m
    print(len(list(combinations(arr, n))))

따라서 임의로 m만큼 배열을 만들어준 후 조합을 할 수 있도록 하였다.
그렇지만 n, m의 수가 커지면 list 생성 시 메모리 에러가 발생할 수 있다. 따라서 이 방법을 이용하지 않고
 
math의 comb를 이용한다.
바로 조합의 개수를 알 수 있다.

import math
t = int(input())
for _ in range(t):
    n, m = map(int, input().split(' '))
    print(math.comb(m, n))

 
까먹어서 이전 풀이를 보고 깨달았다..ㅎ
 
 
참고한 사이트)
https://ourcstory.tistory.com/414

파이썬(Python) 리스트 모든 조합 구하기 (combination vs permutations vs  product)