밑의 링크는 CodeUp에서의 문제 링크입니다.
문제는 링크를 통해서 직접 봐주시길 바랍니다.
nCr (Tiny)
$_nC_r$은 $n$개의 원소를 가지는 집합에서 $r$개의 부분 집합을 고르는 조합의 수를 말한다. $_nC_r$을 일반 공식은 다음과 같다. $_nC_r = \frac{_nP_r}{r!}=\frac{n!}{r!\cdot(n-r)! }$ $_5C_2$는 다음과 같이 구할 수
codeup.kr
주의해야 할 점
1. map, split를 사용하는 입력 방식
실수나 정수인 여러 값들이 입력값일 때,
split 메서드를 사용해 공백이나 어떤 문자를 기준으로 입력값을 여러 값들로 분리하고,
map 내장 함수로 각각의 값들을 int형이나 float형으로 정수, 실수 자료형으로
변환하는 기법은 매우 많이 쓰입니다.
코드 이해부터 하고 나면 다른 문제에서도 외운 듯이 사용해봅시다.
nums = map(int, sys.stdin.readline().split())
2. nCr을 구하는 방법
저는 이번 문제를 풀 때 팩토리얼 계산을 단순히 반복문으로 풀었습니다.
조합을 계산할 때는 문제에서 나와있는 예제와 같이 팩토리얼을 사용하는데,
파이썬에서는 팩토리얼 계산 결과를 반환하는 math 모듈에서 factorial 함수를 제공합니다.
factorial 함수를 사용하면 훨씬 더 쉽게 풀 수 있으니
저처럼 반복문을 사용해서 풀었다면 factorial 함수도 사용해서 풀어보세요.
예제 설명
1. 첫 번째 예제
- 입력
5 2
- 출력
10
- 설명
1 <= r <= n <= 12인 입력한 n과 r은 각각 5, 2입니다.
문제에서 설명한 n=5, r=2일 때 조합 계산식과 결과입니다.
결과가 10이므로 10을 출력합니다.
생각한 풀이 과정
결과값을 저장할 변수 ncr을 선언하고, 곱셈을 누적하는 것이기 때문에 1로 초기화합니다.
nCr의 분자 부분부터 구해봅니다.
1은 곱하나 안 곱하나 상관없으므로 2부터 n까지 반복하면서 ncr에 곱해줍니다.
nCr의 분모 부분도 이어서 계산해봅니다.
2부터 n-r 값까지 반복하면서 ncr을 나누어줍니다.
또 2부터 r 값까지 반복하면서 ncr을 나누어줍니다.
nCr 결과인 ncr 변수의 값을 출력합니다.
제출한 파이썬 코드
# readline을 사용하기 위해 import합니다.
from sys import stdin
# n, r을 공백으로 구분해 입력합니다.
# 1 <= r <= n <= 12
# 각각 int형으로 변환합니다.
n, r = map(int, stdin.readline().split())
# n - r을 구해 변수에 저장합니다.
n_minus_r = n - r
# nCr을 계산한 결과를 저장할 변수를 선언합니다.
# 1로 초기화합니다.
ncr = 1
# nCr의 분자 부분을 계산합니다.
# 2부터 n까지 반복해봅니다.
for num in range(2, n + 1):
# ncr 변수의 값에 현재 숫자를 곱합니다.
ncr *= num
# nCr의 분모 부분을 계산합니다.
# 2부터 n-r까지 반복해봅니다.
for num in range(2, n_minus_r + 1):
# ncr 변수의 값에 현재 숫자를 나눠줍니다.
ncr //= num
# 2부터 r까지 반복해봅니다.
for num in range(2, r + 1):
# ncr 변수의 값에 현재 숫자를 나눠줍니다.
ncr //= num
# nCr 결과인 ncr 변수의 값을 출력합니다.
print(ncr)
제출 결과
댓글