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

조회수 45회

풀려고 하는 알고리즘은

-첫 번째는 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을 입력 받고 재귀함수로 N1이 되거나 2가 되면 1 또는 2를 반환합니다. 그래서 첫번 째 값은 1이 되고 두번 째 값은 2가 됩니다.

그러면 1 2는 구했으니까 문제에서 봤듯이 세번 째부터는 (N-1 * N-2)%100를 구하면 됩니다. 재귀함수로 return Rem(N-1) * Rem(N-2) % 100; 구합니다.

정올 사이트에서 이 코드를 채점하면 TIME LIMIT AXCEED가 뜹니다.. 시간 초과 맞죠?..
메모이제이션을 하려는 데 이해가 가지 않네요..
차근 차근 설명해 주실 분 구합니다 ㅠㅠ

1 답변

  • 좋아요

    2

    싫어요
    채택 취소하기
    #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으로 나눈 나머지를 반환하도록 하면 됩니다.

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

답변을 하려면 로그인이 필요합니다.

Hashcode는 개발자들을 위한 무료 QnA 사이트입니다. 계정을 생성하셔야만 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)

ᕕ( ᐛ )ᕗ
로그인이 필요합니다

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 계정을 생성하셔야만 글을 작성하실 수 있습니다.