수학
-
2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 시간 제한 2초 메모리 제한 128MB 문제 $n \choose m$의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 n, m (0≤m≤n≤2,000,000,000)이 들어온다. 출력 첫째 줄에 $n \choose m$의 끝자리 0의 개수를 출력한다. 예제 입력 1 25 12 예제 출력 1 2 나의 풀이 숫자의 범위가 20억이기 때문에 for문을 통해서 N까지 순회하면 시간 초과가 발생한다. 따라서 5, 2의 인수의 개수를 몫의 성질로 빠르게 구한다. 팩토리얼 0의 개수에선 5의 개수만 알더라도..
[파이썬] 백준 2004번 조합 0의 개수2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 시간 제한 2초 메모리 제한 128MB 문제 $n \choose m$의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 n, m (0≤m≤n≤2,000,000,000)이 들어온다. 출력 첫째 줄에 $n \choose m$의 끝자리 0의 개수를 출력한다. 예제 입력 1 25 12 예제 출력 1 2 나의 풀이 숫자의 범위가 20억이기 때문에 for문을 통해서 N까지 순회하면 시간 초과가 발생한다. 따라서 5, 2의 인수의 개수를 몫의 성질로 빠르게 구한다. 팩토리얼 0의 개수에선 5의 개수만 알더라도..
2022.06.11 -
1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 시간 제한 2초 메모리 제한 128MB 문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력 첫째 줄에 구한 0의 개수를 출력한다. 예제 입력 1 10 예제 출력 1 2 예제 입력 2 3 예제 출력 2 0 나의 풀이 마지막 숫자가 0이려면 10이 곱해져야 함 따라서 팩토리얼 구성 숫자들을 소인수 분해하여 만들 수 있는 10의 개수를 계산하면 됨 N = int(input()) count_2 = 0 count_5 = 0 for i in ra..
[파이썬] 백준 1676번 팩토리얼 0의 개수1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 시간 제한 2초 메모리 제한 128MB 문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력 첫째 줄에 구한 0의 개수를 출력한다. 예제 입력 1 10 예제 출력 1 2 예제 입력 2 3 예제 출력 2 0 나의 풀이 마지막 숫자가 0이려면 10이 곱해져야 함 따라서 팩토리얼 구성 숫자들을 소인수 분해하여 만들 수 있는 10의 개수를 계산하면 됨 N = int(input()) count_2 = 0 count_5 = 0 for i in ra..
2022.06.11 -
문제 확인 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 시간 제한 : 1초 메모리 제한 : 128MB 나의 풀이 못 풀었다. 시도한 풀이는 다음과 같다. 시간 복잡도만 생각하지 말고 메모리도 생각하면서 문제를 풀어야 겠다는 교훈을 얻었다... 여러 타입의 옷이 입력됐을 때 타입의 종류를 조합으로 결정한 뒤 풀이를 시도했다. 타입의 종류가 클 경우 조합 선택 시 메모리 초과가 발생했다. 시간 복잡도 말고 메모리에 대..
[파이썬] 백준 9375번 패션왕 신해빈문제 확인 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 시간 제한 : 1초 메모리 제한 : 128MB 나의 풀이 못 풀었다. 시도한 풀이는 다음과 같다. 시간 복잡도만 생각하지 말고 메모리도 생각하면서 문제를 풀어야 겠다는 교훈을 얻었다... 여러 타입의 옷이 입력됐을 때 타입의 종류를 조합으로 결정한 뒤 풀이를 시도했다. 타입의 종류가 클 경우 조합 선택 시 메모리 초과가 발생했다. 시간 복잡도 말고 메모리에 대..
2022.06.11 -
3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 시간 제한 1초 메모리 제한 128MB 문제 상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다. 링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나..
[파이썬] 백준 3036번 링3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 시간 제한 1초 메모리 제한 128MB 문제 상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다. 링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나..
2022.06.10 -
문제 확인 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 사이트를 방문하여 문제를 확인해주세요. 나의 풀이 시간 초과가 발생하여 결국 풀이를 참고해서 풀었다. 처음엔 바이러스가 곱해지는 비율(거듭 제곱)을 빠르게 구하기 위해서 O(logN)의 시간 복잡도를 가지는 분할 정복을 사용했다. 하지만 N의 범위가 1,000,000이라서 분할 정복 여부는 시간 초과가 관계가 없었다. 결국 큰 수 끼리 곱해지는 과정에서 시간 초과가 발생하게 되는데 큰 수를 어떻게 처리해야할 지 몰랐다. 처음 분할 정복을 시도한 풀이는 다음과 같다. import sys def get_pow(a, b): if b == 0: return 1 # b가 짝수일 경우 elif b % 2 == 0: ret..
[파이썬] 소프티어 바이러스문제 확인 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 사이트를 방문하여 문제를 확인해주세요. 나의 풀이 시간 초과가 발생하여 결국 풀이를 참고해서 풀었다. 처음엔 바이러스가 곱해지는 비율(거듭 제곱)을 빠르게 구하기 위해서 O(logN)의 시간 복잡도를 가지는 분할 정복을 사용했다. 하지만 N의 범위가 1,000,000이라서 분할 정복 여부는 시간 초과가 관계가 없었다. 결국 큰 수 끼리 곱해지는 과정에서 시간 초과가 발생하게 되는데 큰 수를 어떻게 처리해야할 지 몰랐다. 처음 분할 정복을 시도한 풀이는 다음과 같다. import sys def get_pow(a, b): if b == 0: return 1 # b가 짝수일 경우 elif b % 2 == 0: ret..
2022.05.17