시간이 왜 이렇게 오래 걸릴까요?

  • swon31
    swon31

    문제를 풀다가 보니 유독 이 코드에서 시간이 많이나오더라구요 4000ms대..
    제가 이런 쪽은 잘 알지 못하는지라 어느 부분에서 시간을 잡아먹는지 모르겠는데 혹시 원인을 아시는 분 계시면 도움 부탁드립니다

    #include <iostream>
    using namespace std;
    
    double avg(int start, int end, int *cost) {
    
        double sum = 0.0;
        double avg = 0.0;
        for (int i = start; i <= end; i++) {
            sum += cost[i];
        }
        avg = sum / (end - start + 1);
        return avg;
    
    }
    
    double festival(int N, int L, int *cost) {
    
        double currentcost = 0.0;
        double mincost = 999999999999999999999999999999.0;
        for (int i = L; i < N + 1; i++) {
            for (int j = 0; j < N - i + 1; j++) {
                currentcost = avg(j, j + i - 1, cost);
                if (mincost > currentcost)  mincost = currentcost;
            }
        }
    
        return mincost;
    
    }
    
    int main(void) {
        int num;
        int N, L;
    
        cin >> num; //반복 횟수
        for (int i = 0; i < num; i++) {
            cin >> N;
            cin >> L;
            int *cost = new int[N]; //대여비용을 담을 배열
            for (int i = 0; i < N; i++) {
                cin >> cost[i];
            }
            double avgcost = festival(N, L, cost);
            cout.setf(ios::fixed);
    
            cout.precision(11);
            cout << showpoint << avgcost << endl;
            delete cost;
        }
    
        return 0;
    }
    

    8년 전
1개의 댓글이 있습니다.
  • Being
    Being

    알고리즘의 성능이 효율적이지 않아 느린 것입니다.


    8년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.