글 읽기 - C++66퍼에서 계속 시간초과납니다. 이유좀 알려주세요 ㅠㅠ

whitecafe 2년 전 0

시간초과 이유를 모르겠습니다 테케는 모두 통과합니다. cache배열에 메모이제이션 잘 적용한 것 같은데 어디가 틀렸는지 모르겠습니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int buildtime[100001];
int cache[100001];
bool isFriend[1001][1001];
int n;
void initarray()
{
    for(int i = 1;i<=n;i++)for(int j = 1;j<=n;j++)isFriend[i][j] = false;
    for(int i = 1;i<=n;i++)
    {
        buildtime[i] = cache[i] = 0;
    }
}
int f(int v)
{
    if(cache[v]!=0)return cache[v];
    int ret = 0;
    for(int i = 1;i<=n;i++)
    {
        if(isFriend[v][i])
        {
            ret = max(ret,f(i));
        }
    }
    ret += buildtime[v];
    return cache[v] = ret;
}
int main()
{
    int T,k,a,b,final;
    vector<int> res;
    cin>>T;
    for(int times = 1;times<=T;times++)
    {
        cin>>n>>k;
        for(int i = 1;i<=n;i++)cin>>buildtime[i];
        for(int i = 1;i<=k;i++)
        {
            cin>>a>>b;
            isFriend[b][a] = true;
        }
        cin>>final;
        res.push_back(f(final));
        initarray();
    }
    for(int i = 0;i<res.size();i++)
    {
        cout<<res[i]<<endl;
    }
    return 0;
}

iddsi 2년 전 0

극단적인 예를 들어보겠습니다.

N이 1000이고 승리하기 위해 건설해야 할 건물의 번호가 1, 건물간의 건설 순서 규칙이 2 -> 3 ->... 999 -> 1000 -> 1이라고 했을 때

f 함수와 같이 1부터 n까지 전부 탐색을 하게 된다면 첫번째 함수 스택에서 1000번의 연산을, 2번째 함수 스택에서 999번의 연산을, 3번째 함수 스택에서 998번의 연산을,,,,

수행하게 되고, 이는 당연히 시간초과가 발생하게 됩니다. 이보다 훨씬 작은 N에 대해서도 위와 같이 ! 연산을 수행하게 된다면 시간초과가 발생할 수 있습니다.

whitecafe 2년 전 0

감사합니다. 다시한번 생각해보겠습니다.

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

문제

문제

출처

ICPC

C++66퍼에서 계속 시간초과납니다. 이유좀 알려주세요 ㅠㅠ

whitecafe 2년 전 0

iddsi 2년 전 0

whitecafe 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말