무한 수열 A는 다음과 같다.
- A0=1
- Ai=A⌊i/P⌋+A⌊i/Q⌋
정수 N, P와 Q가 주어졌을 때, AN을 구하는 프로그램을 작성하시요.
(단, 0≤N≤1012 이고, 2≤P,Q≤109 이다.)
사고 과정
- 문제가 딱 봐도 재귀적으로 주어져 있으므로, 재귀 함수를 사용하자.
- 그런데 재귀 트리에서 중복되는 문제가 존재하므로, 메모이제이션이 필요하다.
- 상태 공간 범위가 매우 넓다(2≤P,Q≤109). 해시로 DP 하자.
시간 복잡도
1. DP 없이 푼 경우
min(P,Q)=X라 두면, DP 없는 풀이의 시간 복잡도 함수는 다음과 같은 형태로 나타낼 수 있다.
T(N)=2×T(N/X)+1
이러한 형태의 점화식은 마스터 정리로 시간 복잡도를 알아낼 수 있다.
잘 적용해서 계산하면 O(Nlogmin(P,Q)2) 가 나온다.
최대 O(N1) 이라서 시간 초과. (N≤1012)
2. DP 적용한 경우
정답 코드 링크
i번 다음에는 ⌊i/P⌋ 하고 ⌊i/Q⌋ 의 2개의 상태 공간을 방문해야 한다.
이를 i=0이 될 때까지 반복해야 하므로, 최대 logPN+logQN 개의 공간이 있을 것이다.
메모이제이션 덕분에 각 상태 공간을 1번씩만 방문하므로, 시간 복잡도는 O(logN) 이 된다.
실수한 점
함수 형식인자에 int
쓰고 실인자에는 long long
전달하는 실수를 저질렀다.
long long
쓰는 문제는 반드시 제출 전에 Ctrl+F
로 모든 int
를 찾아 바꿔서 제출하자.
이것 때문에 푸는데 10분 넘게 걸렸음.