글 읽기 - 1351 무한수열 시간초과 해결 방법이 뭐가 있을까요...?

20151571 8년 전 0

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

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

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

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

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

#include <stdio.h>
long long int N,P,Q;
long long int dp(long long int n){
	if(n==0){
		return 1;
	}
    if(n==1){
        return 2;
    }
	long long int ans = dp(n/P)+dp(n/Q);
	return ans;
}

int main(){
	scanf("%lld %lld %lld",&N,&P,&Q);
	printf("%lld\n",dp(N));
	return 0;
}

yukariko 8년 전 0

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

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

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

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

yukariko 8년 전 0

다른 분의 풀이를 보니

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

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

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

20151571 8년 전 0

감사합니다

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

문제

문제

출처

ICPC

1351 무한수열 시간초과 해결 방법이 뭐가 있을까요...?

20151571 8년 전 0

yukariko 8년 전 0

yukariko 8년 전 0

20151571 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말