[실버 2] 백준 17213 - 과일 서리 (파이썬)

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

풀이

서로 다른 N개의 과일 중에서 M개를 훔쳐올 때, 적어도 1개씩은 훔치는 경우의 수를 구하는 문제이다.

적어도 1개씩 N종료의 과일을 가져온다는 조건은 곧 M개의 과일을 N개의 상자에 각각 적어도 1개씩 넣는 방법의 수를 묻는 것과 같다.

이는 중복 조합의 문제로 환원되며, 중복 조합의 식은 다음과 같다.

answer = 1
for i in range(1, M - N + 1) :
    answer *= (M - i)
    answer //= i

위 코드는 nCr의 계산 중에서 n = M - 1, r = M - N을 계산하는 것이다.

파이썬 내장 함수 없이 직접 계산이 가능하다. (Collection 모듈)

코드

# 백준 17213 - 과일 서리
# 분류 : 다이나믹 프로그래밍

N = int(input())
M = int(input())

# M - 1 C M - N
answer = 1
for i in range(1, M - N + 1) :
    answer *= (M - i)
    answer //= i

print(answer)