[πŸ™ μ•Œκ³ λ¦¬μ¦˜] λ°±μ€€ 1010 - 닀리놓기 / Python

dsfasdΒ·2022λ…„ 11μ›” 2일
0

문제

μž¬μ›μ΄λŠ” ν•œ λ„μ‹œμ˜ μ‹œμž₯이 λ˜μ—ˆλ‹€. 이 λ„μ‹œμ—λŠ” λ„μ‹œλ₯Ό 동μͺ½κ³Ό μ„œμͺ½μœΌλ‘œ λ‚˜λˆ„λŠ” 큰 일직선 λͺ¨μ–‘μ˜ 강이 흐λ₯΄κ³  μžˆλ‹€. ν•˜μ§€λ§Œ μž¬μ›μ΄λŠ” 닀리가 μ—†μ–΄μ„œ μ‹œλ―Όλ“€μ΄ 강을 κ±΄λ„ˆλŠ”λ° 큰 λΆˆνŽΈμ„ κ²ͺκ³  μžˆμŒμ„ μ•Œκ³  닀리λ₯Ό μ§“κΈ°λ‘œ κ²°μ‹¬ν•˜μ˜€λ‹€. κ°• μ£Όλ³€μ—μ„œ 닀리λ₯Ό 짓기에 μ ν•©ν•œ 곳을 μ‚¬μ΄νŠΈλΌκ³  ν•œλ‹€. μž¬μ›μ΄λŠ” κ°• 주변을 λ©΄λ°€νžˆ 쑰사해 λ³Έ κ²°κ³Ό κ°•μ˜ μ„œμͺ½μ—λŠ” N개의 μ‚¬μ΄νŠΈκ°€ 있고 동μͺ½μ—λŠ” M개의 μ‚¬μ΄νŠΈκ°€ μžˆλ‹€λŠ” 것을 μ•Œμ•˜λ‹€. (N ≀ M)

μž¬μ›μ΄λŠ” μ„œμͺ½μ˜ μ‚¬μ΄νŠΈμ™€ 동μͺ½μ˜ μ‚¬μ΄νŠΈλ₯Ό λ‹€λ¦¬λ‘œ μ—°κ²°ν•˜λ €κ³  ν•œλ‹€. (μ΄λ•Œ ν•œ μ‚¬μ΄νŠΈμ—λŠ” μ΅œλŒ€ ν•œ 개의 λ‹€λ¦¬λ§Œ 연결될 수 μžˆλ‹€.) μž¬μ›μ΄λŠ” 닀리λ₯Ό μ΅œλŒ€ν•œ 많이 μ§€μœΌλ €κ³  ν•˜κΈ° λ•Œλ¬Έμ— μ„œμͺ½μ˜ μ‚¬μ΄νŠΈ 개수만큼 (N개) 닀리λ₯Ό μ§€μœΌλ €κ³  ν•œλ‹€. λ‹€λ¦¬λΌλ¦¬λŠ” μ„œλ‘œ 겹쳐질 수 μ—†λ‹€κ³  ν•  λ•Œ 닀리λ₯Ό 지을 수 μžˆλŠ” 경우의 수λ₯Ό κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜λΌ.


μ½”λ“œ

import sys
input = sys.stdin.readline
import math

t = int(input())

for i in range(t): #ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€ 만큼 반볡
    cases = list(map(int,input().split()))

    print(math.comb(cases[1], cases[0]))

풀이

μ‘°ν•© 곡식을 μ΄μš©ν•΄μ„œ ν‘ΈλŠ” λ¬Έμ œμ΄λ‹€.

μ‘°ν•© : n개 쀑 r개λ₯Ό λ½‘λŠ” 경우의 수
nCr = (nβˆ’r)! / r!n!

math λͺ¨λ“ˆ 쀑 comb을 μ΄μš©ν•˜λ©΄ μ‘°ν•© 곡식을 νŽΈλ¦¬ν•˜κ²Œ μ‚¬μš©ν•  수 μžˆλ‹€.
math.comb(n, r) // n개 μ€‘μ—μ„œ r개λ₯Ό 선택

profile
기둝을 μ •λ¦¬ν•˜λŠ” 곡간!

0개의 λŒ“κΈ€