구슬을 나누는 경우의 수
2024. 7. 31. 18:00ㆍ코딩테스트 입문
https://school.programmers.co.kr/learn/courses/30/lessons/120840
문제 설명
머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수 balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 return 하는 solution 함수를 완성해주세요.
제한사항
- 1 ≤ balls ≤ 30
- 1 ≤ share ≤ 30
- 구슬을 고르는 순서는 고려하지 않습니다.
- share ≤ balls
입출력 예
balls | share | result |
3 | 2 | 3 |
5 | 3 | 10 |
입출력 예 설명
입출력 예 #1
- 서로 다른 구슬 3개 중 2개를 고르는 경우의 수는 3입니다.
입출력 예 #2
- 서로 다른 구슬 5개 중 3개를 고르는 경우의 수는 10입니다.
Hint
- 서로 다른 n개 중 m개를 뽑는 경우의 수 공식은 다음과 같습니다.
고등학생 때 배우는 수학이 생각나는 문제입니다.
순열은 nPr, 조합은 nCr. 이 문제는 조합이므로 nCr로, balls는 n, share은 r이라 생각할 수 있습니다.
파이썬으로 조합의 개수를 구해보도록 하겠습니다.
def solution(balls, share):
# 분자, 분모 초기화
denom, numer = 1, 1
# nCr 공식대로 분자 분모 설정
for i in range(balls - share + 1, balls + 1):
denom *= i
for i in range(1, share + 1):
numer *= i
# 답 = 분자 / 분모
answer = denom / numer
return answer
파이썬의 특징은 없는 함수가 없다는 점이죠. math 함수에서 사용하는 comb(n, k) 함수는 nCk의 결과를 반환합니다.
# math 패키지에서 comb 함수만 가져온다.
from math import comb
def solution(balls, share):
# 답 = nCr의 결과
answer = comb(balls, share)
return answer
이렇게 함수를 사용해서도 문제를 풀 수 있습니다.