글 읽기 - 안녕하세요 메모이제이션에 대해 질문 드립니다.

qqa12345 3년 전 0

여러 질문을 보니 제 풀이와는 다르게 메모이제이션을 통한 풀이를 요구하는 것 같던데

문제에서 테스트 케이스의 수가 무한으로 주어진 것이 바로 그 이유인가요??

그렇다면 제 풀이는 n이 40이 아니라 훨씬 큰 수가 주어진다면 오답 처리가 될 수도 있는건가요?

#include <iostream>
int main()
{
    long long t, n, sum, sum_1= 1, sum_2 = 0;
    scanf("%lld", &t);
    for(int i=0; i<t; i++)
    {
        scanf("%lld", &n);
        for(int q=0; q<=n; q++)
        {
            if(n == 0)
            {
                printf("1 0\n");
                break;
            }
            if(n == 1)
            {
                printf("0 1\n");
                break;
            }
            if(q == 0 || q == 1)
                continue;
            
            sum = sum_2 + sum_1;
            if(q == n)
            {
                printf("%lld %lld\n", sum_1, sum);
            }
                sum_2 = sum_1;
                sum_1 = sum;
        }
        sum_1 = 1;
        sum_2 = 0;
    }
    
    return 0;
}

sait2000 3년 전 1

메모이제이션을 이용한 풀이나 이 풀이나 T가 1이면 시간복잡도는 O(N)이 됩니다. 그러니까 제 말은 N에 비례하는 시간이 걸립니다.

이 풀이도 조금의 노력을 하면 모든 피보나치 수를 배열에 저장한다던가 하는 식으로 어렵지 않게 중복되는 계산을 줄일 수 있습니다.

N이 엄청 커진다는 게 어떤 정도의 크기를 말씀하시는 건지는 모르겠지만 행렬 곱셈을 이용해서 O(log N)에 계산하는 방법이 있습니다.

qqa12345 3년 전 0

감사합니다. 제가 지식이 부족하다보니 질문도 이해하기 어렵게 했는데
좋은 답변 감사합니다!!

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

문제

문제

출처

ICPC

안녕하세요 메모이제이션에 대해 질문 드립니다.

qqa12345 3년 전 0

sait2000 3년 전 1

qqa12345 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말