본문 바로가기

Algorithms63

백준 2004. 조합 0의 개수 https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 당연하지만 일반 팩토리얼로 풀리지 않는다. 그래서 조합 공식인 n!/r!(n-r)!에서, 분자에서의 2와 5의 수, 분모에서의 2와 5의 수를 찾아서 뺄 생각을 했다. 10^n승은 (2x5)^n이므로 2와 5 중에 더 적은 녀석만 구해준다면 10의 계수를 알 수 있다. 다만 구현하는 데 좀 애를 먹었다. def count_two(n): count = 0 while n != 0: count += n//2 n //=2 return count def count_.. 2022. 6. 15.
백준 1676. 팩토리얼 0의 개수 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 소개에는 소인수분해를 통하여 0의 개수를 알아내는 문제라고 써있던데.. 그래서 소인수분해로 접근해봤을 때, 2, 5의 쌍의 개수만큼 0의 개수가 있을 것이라는 결론에 도달했다. 다만 이를 실제로 구현하지는 않았고, 단순히 10으로 나눈 나머지가 0이 아니게 될 때까지(끝자리가 0이 아닌 정수가 나올 때까지) 나눠버리고 카운트를 해봤다. import math n = int(input()) n_fac = math.factorial(n) count = 0 while n_fac % 1.. 2022. 6. 14.
백준 9375. 패션왕 신해빈 https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 간단한 경우의 수 문제. 각 카테고리의 옷들에 대해서 경우의 수를 따져주면 되는데, 모든 옷을 따로 입는 게 아닌 동시에 입는 것이기 때문에 곱의 법칙을 이용해야 한다. 다만 그냥 곱하는 건 안 되고, 해당 카테고리의 옷을 입을 수도 안 입을 수도 있기 때문에 각 카테고리마다 +1을 해준 값을 곱하고, 문.. 2022. 6. 13.
백준 1010. 다리 놓기 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 간단한 조합 문제. 총 M개의 강 건너편에 있는 다리 중에서 N개를 뽑아 만드는 경우의 수를 출력해주면 된다. from math import * n = int(input()) for i in range(n): N, M = map(int, input().split()) print(factorial(M) // (factorial(N) * factorial(M - N))) 2022. 6. 12.

티스토리툴바