본문 바로가기

전체 글92

백준 15650. N과 M(2) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net NPM 중에서도 오름차순으로 정렬되어 있는 수열만 출력하는 문제. 수열을 만드는 문제들에서 주로 쓰이는 DFS(Depth First Search, 깊이우선탐색)를 사용했다. 기본적인 개념은 다음과 같다. [1]에서 시작해서 두번째 숫자에 우선 1을 넣는다. [1,1] -> 끝자리에 1~9를 모두 넣어본다. 한칸 후퇴해서 [1,2] 로 리스트를 바꾼다. ->다시 끝자리에 1~9를 모두 넣어본다. .. 2022. 6. 16.
백준 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.

티스토리툴바