[백준] 13439. 팩토리얼과 점화식

https://www.acmicpc.net/problem/13439

문제요약

• 점화식이 주어짐
• S(n, k)의 약수 개수 구하기

접근법

• S(X, 1) = X! 임을 이용함
• 점화식을 진행하다가 보면 언젠가는 X! 모양이 될 것임
• 미리 X!이 어떤 소인수로 구성되어있는지 구해놓음
  • 2! : [1, ...]
  • 3! : [1, 1,...]
  • 4! : [3, 1, ....]
  • 1000! : [....]
• 1000까지의 소수의 개수는 168개
• S(a, b)는 계산결과를 소인수 분해한 결과를 반환 = 168크기의 배열. 각각은 2, 3, 5, ... 인수의 개수
• S(a, b) = S(a, b - 1)과 S(a - 1, b) 배열의 합
• 메모리 절약을 위해 a를 증가시켜가면서 이전과 현재만 저장
• ${O(N * K * 168) = 1000 * 100 * 168 = 1.6천만}$