[BOJ] 1351번: 무한 수열

copyrat90·2022년 3월 11일
0

PS

목록 보기
1/5

문제 설명

무한 수열 AA는 다음과 같다.

  • A0=1A_0 = 1
  • Ai=Ai/P+Ai/QA_i = A_{\lfloor i/P \rfloor} + A_{\lfloor i/Q \rfloor}

정수 NN, PPQQ가 주어졌을 때, ANA_N을 구하는 프로그램을 작성하시요.
(단, 0N10120 \le N \le 10^{12} 이고, 2P,Q1092 \le P, Q \le 10^9 이다.)

사고 과정

  1. 문제가 딱 봐도 재귀적으로 주어져 있으므로, 재귀 함수를 사용하자.
  2. 그런데 재귀 트리에서 중복되는 문제가 존재하므로, 메모이제이션이 필요하다.
  3. 상태 공간 범위가 매우 넓다(2P,Q109)(2 \le P, Q \le 10^9). 해시로 DP 하자.

시간 복잡도

1. DP 없이 푼 경우

min(P,Q)=X\min(P,Q)=X라 두면, DP 없는 풀이의 시간 복잡도 함수는 다음과 같은 형태로 나타낼 수 있다.

T(N)=2×T(N/X)+1T(N)=2 \times T(N/X) + 1

이러한 형태의 점화식은 마스터 정리로 시간 복잡도를 알아낼 수 있다.

잘 적용해서 계산하면 O(Nlogmin(P,Q)2)O(N^{\log_{\min(P,Q)} 2}) 가 나온다.
최대 O(N1)O(N^1) 이라서 시간 초과. (N1012)(N \le 10^{12})

2. DP 적용한 경우

정답 코드 링크

ii번 다음에는 i/P\lfloor i/P \rfloor 하고 i/Q\lfloor i/Q \rfloor 의 2개의 상태 공간을 방문해야 한다.
이를 i=0i=0이 될 때까지 반복해야 하므로, 최대 logPN+logQN\log_P N + \log_Q N 개의 공간이 있을 것이다.
메모이제이션 덕분에 각 상태 공간을 1번씩만 방문하므로, 시간 복잡도는 O(logN)O(\log N) 이 된다.

실수한 점

함수 형식인자에 int 쓰고 실인자에는 long long 전달하는 실수를 저질렀다.
long long 쓰는 문제는 반드시 제출 전에 Ctrl+F 로 모든 int를 찾아 바꿔서 제출하자.

이것 때문에 푸는데 10분 넘게 걸렸음.

profile
요새 알고리즘 문제 푸는 초보A

0개의 댓글