[python]백준 1010번: 다리 놓기(Combination)

# 1010 다리 놓기

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

1010번: 다리 놓기

코드

import math

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

📝 풀이

강을 기준으로 n이 서쪽이고 m이 동쪽이다. m에서 겹치지 않게 n만큼 뽑아주면 된다.

예제를 보면 2C2, 5C1, 29C13와 같은 값이 나온다.

그래서 딱 보자마자 조합 문제이니까 combination을 쓰면 되겠구나 싶었다.

from itertools import *

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

그래서 다음과 같이 코드를 작성했는데, 1번과 2번 케이스는 나오지만 3번째 케이스에서 말도 안되게 느리게 나왔고 실제로 제출하면 시간초과 결과가 나온다.

⭐ 파이썬 조합 구하기

파이썬 내장 라이브러리인 itertools를 사용하면 조합을 아주아주 쉽게 구할 수 있다.

from itertools import permutations
from itertools import combinations
from itertools import product

하나의 리스트에서 모든 조합을 계산해야 한다면 permutations와 combinations, 두개 이상의 리스트에서 모든 조합을 계산해야 한다면 product를 사용하면 된다.

combinations

dp = [1,2,3,4]
print(list(combinations(dp, 2)))
# [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

combinations를 사용하면 중복되지 않은 조합들을 모두 출력해준다. 

permutations

dp = [1,2,3,4]
print(list(permutations(dp, 2)))
# [(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]

permutations을 사용하면 중복을 포함한 조합을 모두 출력해준다.

product

dp = [[1,2,3],['A', 'B']]
print(list(product(*dp)))
# [(1, 'A'), (1, 'B'), (2, 'A'), (2, 'B'), (3, 'A'), (3, 'B')]

두개 이상의 리스트의 조합을 구할 때에는 product를 사용하면 구할 수 있다.

🔓 코드 뜯어보기

import math

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

다시 본론으로 돌아와서 내가 알고 있던 3가지의 방법으로 코드를 작성했더니 시간초과가 나왔다. 구글링을 해보니 더 괜찮은 math.comb라는 방법이 있었다. math.comb(m, n)을 사용하면 m개에서 n개를 조합으로 선택할 때의 경우의 수를 출력한다(nCk과 같은 조합 값을 반환한다. (n개의 수에서 k개를 선택)).