c언어 재귀함수 time limit axceed 질문

Question

c언어 재귀함수 time limit axceed 질문

조회수 618회

c

recursive

0

싫어요

풀려고 하는 알고리즘은

-첫 번째는 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가 뜹니다.. 시간 초과 맞죠?..
메모이제이션을 하려는 데 이해가 가지 않네요..
차근 차근 설명해 주실 분 구합니다 ㅠㅠ

엽토군 9,979 points

2020-02-12 19:28:36에 수정됨
(•́ ✖ •̀)
알 수 없는 사용자
〉

댓글 입력

score 2 · Accepted Answer

#include <stdio.h>

int recur(int n, int *arr){
    if (n == 1){
        return 1;
    }
    else if (n == 2){
        arr[0] = 1;
        return 2;
    }else{
        arr[n-2] = recur(n-1, arr);
        return arr[n-2] * arr[n-3] % 100;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    printf("%d\n", recur(n, &arr));

    return 0;
}

더 깔끔하게 작성할수도 있었겠지만 그래도 통과 되는건 확인했습니다

재귀함수에서 자기자신을 2번 호출하게 되면 숫자가 커질수록 자신을 호출하는 횟수가 엄청나게 많이 늘어나게 되기 때문에 메모이제이션을 사용하는데요,

입력값의 크기만큼 배열을 선언해준 후에 초기 두 케이스는 1과 2를 반환, 나머지 케이스는 n을 1 감소시킨 재귀함수를 호출한 후 이 값을 배열의 다음 칸에 저장하고 문제에서 요구한대로 해당 배열값과 그 전 배열값의 곱을 100으로 나눈 나머지를 반환하도록 하면 됩니다.

(질문하는 칸을 못 찾겠어서... 여기다 질문 합니다) 어.. 이 주제와는 다른 질문인데요. 이 알고리즘은 수준이 어느정도로 보시나요? 하 중하 중 중상 상에서