백준 1010 다리 놓기 Python

🐸 문제 정보

1010번: 다리 놓기

 

🤖 알고리즘

DP

(라고 하지만, 그냥 수학으로 풀었다.)

 

⏱️ 풀이 시간

약 10m

(중간에 맥 업데이트 오류때문에 잠깐 멈추고 체크를 안함..)

 

📝 풀이

보자마자 조합문제다! 싶었다.

mCn 으로 풀면 되지만, 문제는 itertools의 combinations를 이용하면 세 번째 테케에서 엄청나게 오래 걸린다.

그래서 직접 수를 구해야하나? 싶었지만, math.comb 모듈이 있었다.

이 모듈은 조합을 뽑아주는게 아니라, 조합의 경우의 수를 알려주는 모듈이다.

DP로 풀 수 있다고 하는데, 굳이.. 싶어서 그냥 여기까지 풀고 끝냈다.

 

🧑‍💻 나의 답

# pypy3

import sys
from math import comb
input = sys.stdin.readline

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