📌 문제 : 백준 11050번
📌 문제 탐색하기
N : 자연수 (1 ≤ N ≤ 10)
K : 정수 (0 ≤ K ≤ N)
✅ 입력 조건
1.N,K공백으로 구분해 입력
✅ 출력 조건
1. 이항 계수 계산해 출력
이항 계수란,
주어진 집합에서 원하는 개수만큼 순서 없이 뽑는 조합의 개수이다.
즉, 서로 다른 n개의 물건 중에서 k개를 뽑는 경우의 수와 같다.
정의를 식으로 표현하면 다음과 같다.
저 수식을 그대로 구현한다.
먼저, 팩토리얼을 구하는 함수를 정의한 후 수식대로 식을 만들어주어 이항 계수 값을 구한다.
가능한 시간복잡도
팩토리얼 함수 →
최종 시간복잡도
이고 1 ≤ N ≤ 10이므로 제한 시간 내에 연산이 가능하다.
알고리즘 선택
팩토리얼 함수를 구현해 이항 계수 계산하기
📌 코드 설계하기
- N, K 입력
- 팩토리얼 정의
- 이항 계수 계산
- 원하는 형식으로 출력
📌 시도 회차 수정 사항
1회차
📌 정답 코드
import sys
input = sys.stdin.readline
# N, K 입력
N, K = map(int, input().split())
# 팩토리얼 정의
def factorial(n):
ans = 1
for i in range(2, n+1):
ans *= i
return ans
# 이항 계수 계산
answer = factorial(N) // (factorial(N-K) * factorial(K))
# 원하는 형식으로 출력
print(answer)- 결과
다른 풀이 1
#### 팩토리얼 재귀 함수 정의해 풀기
import sys
input = sys.stdin.readline
# N, K 입력
N, K = map(int, input().split())
# 팩토리얼 정의
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n-1)
# 이항 계수 계산
answer = factorial(N) // (factorial(N-K) * factorial(K))
# 원하는 형식으로 출력
print(answer)- 결과
- 기존 코드를 재귀식으로 변경한 코드이다.
다른 풀이 2
#### 파스칼의 삼각형을 사용한 DP 방법으로 풀기
import sys
input = sys.stdin.readline
# N, K 입력
N, K = map(int, input().split())
# DP 테이블 초기화
DP = [[0] * (N + 1) for _ in range(N + 1)]
# 파스칼의 삼각형을 이용한 DP 테이블 채우기
for i in range(N + 1):
DP[i][0] = 1 # nC0는 항상 1
DP[i][i] = 1 # nCn은 항상 1
for i in range(2, N + 1):
for j in range(1, i):
DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j]) % 10007 # 중간 값들도 모듈러 연산 적용
# 원하는 형식으로 출력
print(DP[N][K] % 10007)- 결과
- 파스칼의 삼각형을 적용해 이항 계수들을 구한 뒤 원하는 답을 출력하는 식으로 구현된 DP 풀이이다.
- 모듈러 연산이 적용되어 있는데 이항 계수를 구하다보면 매우 큰 숫자가 나올 수 있어서 overflow가 발생할 수 있다고 한다. 이를 방지하기 위해 적용된다.
📌 회고
- 이항 계수 식대로 팩토리얼을 이용해 푸는 방법만 알고 있었는데, 파스칼의 삼각형을 통해 DP로 풀 수 있다는 것이 신기했다.
- 모듈러 연산에 대해 처음 찾아보게 되었는데 아직 적용에 대해서 이해가 잘 안되었다.
- 모듈러 연산
- 어떤 숫자를 다른 숫자로 나눈 나머지를 구하는 연산(mod)이다.
- 큰 수 연산에 도움을 준다.
- 예시
r = a % m = a mode m
