글 읽기 - c언어 시간초과 다이나믹 프로그래밍 사용한 것 같은데 왜 이럴까요?

skiwer98 2년 전 0

다이나믹프로그래밍을 사용한다고 한건데 시간초과가 뜹니다. 어디서 뜬걸까요?

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int dp[41];
int dp0[41];
int dp1[41];

void fibo(int n)
{
    if (n == 0)
    {
        dp[0] = 0;
        dp0[0] = 1;
        return;
    }

    if (n == 1)
    {
        dp[1] = 1;
        dp1[1] = 1;
        return;
    }

    if (dp[n] != 0)
        return;
    
    else
    {
        fibo(n - 1);
        fibo(n - 2);
        dp0[n] = dp0[n - 1] + dp0[n - 2];
        dp1[n] = dp1[n - 1] + dp1[n - 2];
        return;
    }
}


int main()
{
    int testnum;
    scanf("%d", &testnum);
    int k;

    for (int i = 0; i < testnum; i++)
    {
        memset(dp, 0, sizeof(dp));
        memset(dp0, 0, sizeof(dp0));
        memset(dp1, 0, sizeof(dp1));
        scanf("%d", &k);
        fibo(k);
        printf("%d %d\n", dp0[k], dp1[k]);
    }

    return 0;
}

amsminn 2년 전 0

모든 테스트케이스마다 디피를 새로 계산해주면 의미가 없습니다.

시간복잡도는 O(NT)가 되고요.

피보나치의 값은 언제 어떤 상황에서 계산하던 같은 값이기 때문에 dp배열을 초기화할 필요가 없습니다.

또한 초기화를 하지 않아야 시간복잡도 또한 O(N + T)가 보장됩니다.

djm03178 2년 전 1

윗분 말씀도 맞지만, 시간 복잡도 O(NT) 정도로는 이 문제에서 시간 초과가 될 정도는 아닙니다.

이 코드의 문제점은 애초에 메모이제이션이 올바르게 수행되지 않았다는 점입니다. 이미 계산한 값인지를 보기 위해 dp[n]이 0이 아닌지를 확인하고 있는데, 실제로는 dp 배열에는 dp[0]과 dp[1]에만 값을 넣고 있고 2부터 n까지는 dp0과 dp1 배열에만 값을 넣고 있어 이미 계산한 값인지 알 수 없게 됩니다. 결국 완전탐색을 하는 거나 다름없는 코드입니다.

skiwer98 2년 전 0

그렇네요 해결됐습니다.

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

문제

문제

출처

ICPC

c언어 시간초과 다이나믹 프로그래밍 사용한 것 같은데 왜 이럴까요?

skiwer98 2년 전 0

amsminn 2년 전 0

djm03178 2년 전 1

skiwer98 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말