20151571   11달 전

50~60% 정도에서 시간 초과가 뜨길래

P,Q는 2이상이기 때문에 n이 1이 되면 2를 리턴하는 식으로 해보았는데도

73%~74% 정도에서 시간 초과가 떠버네요.

이 방법으로는 절대 해결 할 수 없는 것인가요??

다른 방법으로는 뭐가 있을 까요?

yukariko   11달 전

범위가 10^9 라서 모든 범위에 대해 dp 배열을 잡을 수는 없지만,

재귀 함수에 들어가는 인자가 항상 나눗셈을 통해 숫자가 크게 줄어들기 때문에

적당한 범위만큼은 dp 배열을 통해 반복을 줄이고, 

그걸 초과하는 범위에선 재귀연산을 수행하게 해주면 정답을 받을 수 있을것입니다.

yukariko   11달 전

다른 분의 풀이를 보니

n이 p와 q에 대한 지수만큼 감소하는것을 이용해서

지수에 대한 dp를 적용하여 문제를 해결하였네요.

이 방법이 정해인것 같습니다.

20151571   11달 전

감사합니다

댓글을 작성하려면 로그인해야 합니다.