일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
- AI 경진대회
- leetcode
- 맥북
- 파이썬
- gs25
- dacon
- ChatGPT
- 데이콘
- 더현대서울 맛집
- PYTHON
- 백준
- Real or Not? NLP with Disaster Tweets
- 프로그래머스 파이썬
- SW Expert Academy
- 금융문자분석경진대회
- 우분투
- 캐치카페
- programmers
- 프로그래머스
- Baekjoon
- Git
- hackerrank
- 자연어처리
- 편스토랑 우승상품
- Docker
- ubuntu
- github
- Kaggle
- 편스토랑
- 코로나19
- Today
- Total
솜씨좋은장씨
[BaeKJoon] 2004번: 조합 0의 개수 (Python) 본문

1일 최소 1문제 4일차!
오늘의 문제는 조합 속의 0의 개수를 구하는 문제입니다.
2004번: 조합 0의 개수
첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다.
www.acmicpc.net


먼저 nCk일 경우 왼쪽과 같이 연산을 실시합니다.
여기서 n이 10 k가 7일 경우 10!을 3!과 7!로 나누어 계산합니다.
이를 인지하고 이전에 풀었던 팩토리얼 문제를 활용하여 풀어보려합니다.
[BaeKJoon] 10872번: 팩토리얼 (Python)
1일 최소 1문제! 3일차! 이미 오늘 문제의 할당량은 채웠지만 원자력발전소 상태판단 알고리즘 상태판단 경진대회를 위해 LightGBM 모델을 학습시키고 있는데 시간이 너무 오래걸려 그 시간 사이에 문제를 풀어보..
somjang.tistory.com
def factorialNum(N):
if N == 0 or N == 1:
return 1
else:
fact = 1
for i in range(1, N + 1):
fact = fact * i
return fact
def factorialTopNum(N, M):
top = 1
for i in range(N-M+1, N+1):
top = top * i
return top
N, M = map(int, input().split())
combination = int(factorialTopNum(N, M) / factorialNum(M))
print(combination)
comb_list = list(str(combination))
comb_list_len = len(comb_list)
count = 0
for i in range(len(comb_list)):
if comb_list[comb_list_len-1-i] !='0':
break
elif comb_list[comb_list_len-1-i] == '0':
count = count + 1
print(count)
결과는!

m과 n으로 들어오는 숫자가 (0≤m≤n≤2,000,000,000, n!=0) 이므로
엄청나게 큰 숫자가 들어오게 되면 시간초과가 발생하는 것 같습니다.
이문제는 조합을 구해서 답을 내는 것이아닌 조합 내의 0의 개수를 구하는 문제이므로
이번에는 나눗셈은 지수의 차의 개념과
팩토리얼 내의 0을 만들 수 있는 2와 5의 개수를 가지고 풀어보았습니다.

M과 N을 입력받았을떄 M! 을 N!과 (M-N)!로 나눈 값이 조합입니다.
그럼 여기서 0의 개수를 구하는 것은
0의개수
=
M!가 가지고 있는 2의 개수 - N!이 가지고 있는 2의 개수 - (M-N)!이 가지고 있는 2의 개수
/
M!가 가지고 있는 5의 개수 - N!이 가지고 있는 5의 개수 - (M-N)!이 가지고 있는 5의 개수
중에 작은 수
가 됩니다.
이것을 코드로 구현하면
def countNum(N, num):
count = 0
divNum = num
while( N >= divNum):
count = count + (N // divNum)
divNum = divNum * num
return count
M, N = map(int, input().split())
print(min(countNum(M, 5) - countNum(N, 5) - countNum(M-N, 5), countNum(M, 2) - countNum(N, 2) - countNum(M-N, 2)))

생각을 바꾸니 해결할 수 있었습니다.
SOMJANG/CODINGTEST_PRACTICE
1일 1문제 since 2020.02.07. Contribute to SOMJANG/CODINGTEST_PRACTICE development by creating an account on GitHub.
github.com
'Programming > 코딩 1일 1문제' 카테고리의 다른 글
[BaeKJoon] 11650번: 좌표 정렬하기 (Python) (2) | 2020.02.11 |
---|---|
[BaeKJoon] 2751번: 수 정렬하기2 (Python) (0) | 2020.02.11 |
[BaeKJoon] 1676번: 팩토리얼 0의 개수 (Python) (2) | 2020.02.09 |
[BaeKJoon] 10872번: 팩토리얼 (Python) (0) | 2020.02.09 |
[BaeKJoon] 11653번: 소인수분해 (Python) (0) | 2020.02.09 |