풀려고 하는 알고리즘은
-첫 번째는
1, 두 번째는2, 세 번째부터는 앞의 두 수의 곱을100으로 나눈 나머지로 이루어진 수열이 있다.
100이하의 자연수N을 입력받아 재귀함수를 이용하여 N번째 값을 출력하는 프로그램을 작성하시오.입력: 5
출력: 8
(1 2 2 4 8 32 56 92 ..)
#include <stdio.h>
int Rem(int N)
{
if(N == 1)
return 1;
if(N == 2)
return 2;
return Rem(N-1) * Rem(N-2) % 100;
}
int main(void)
{
int N;
scanf("%d", &N);
printf("%d", Rem(N));
return 0;
}
N을 입력 받고 재귀함수로 N이 1이 되거나 2가 되면 1 또는 2를 반환합니다. 그래서 첫번 째 값은 1이 되고 두번 째 값은 2가 됩니다.
그러면 1 2는 구했으니까 문제에서 봤듯이 세번 째부터는 (N-1 * N-2)%100를 구하면 됩니다. 재귀함수로 return Rem(N-1) * Rem(N-2) % 100; 구합니다.
정올 사이트에서 이 코드를 채점하면 TIME LIMIT AXCEED가 뜹니다.. 시간 초과 맞죠?..
메모이제이션을 하려는 데 이해가 가지 않네요..
차근 차근 설명해 주실 분 구합니다 ㅠㅠ