[백준 15996번 팩토리얼 나누기]
오늘의 문제는 팩토리얼 나누기이다. 처음엔 무조건 완전탐색!N의 범위가 int범위 끝이니 약 21억쯤으로 1부터 최대범위까지 탐색하며될 때마다 세준다면 필연적으로 시간초과가 날 것이다. 고민 끝에 알아낸 것은?모든 수를 확인할 필요 없이 A가 N까지 모든 수 중에몇 개가 포함되어 있나? 였다. 예를 들어, N = 10이라면2, 4, 6, 8, 10에 각각 1, 2, 1, 3, 1개씩 2가 들어있고,이는 N까지의 모든 2의 제곱수(문제의 A의 제곱수)로 N을 나누고그 수를 ans에 모두 더해주면 끝이다! 방금 얘기한 N = 10인 경우,10 / 2 = 510 / 4 = 210 / 8 = 1(나눈 값이 int자료형인 것에 유의하자!)합하면? 8! 예시를 한 가지 더해보자,N = 15, A = 3인 경우15..
2025. 1. 5.
