글 읽기 - 7469 C언어 시간초과

youk6767 3년 전 0

시간초과가 발생하는 이유가 무엇인가요..??

#include <stdio.h>
#include <stdlib.h>

int F(const void* a, const void* b){
        return *(int*)a-*(int*)b;
}
int main(void){
        int n,m,a,b,c;
        scanf("%d %d",&n,&m);
        int A[n];
        for(int i=0;i<n;i++) scanf("%d", &A[i]);
        for(int i=0;i<m;i++){
                scanf("%d %d %d",&a,&b,&c);
                int B[b-a+1],k=0;
                for(int j=a-1;j<b;j++){
                        B[k]=A[j];
                        k++;
                }
                qsort(B,b-a+1,sizeof(int),F);
                printf("%d\n", B[c-1]);
        }
return 0;
}

현재 코드의 시간복잡도는 O(NQ log N)입니다. 왜냐하면 각각 쿼리마다 정렬을 하기 때문에 여기서 NlogN이고, Q번의 쿼리가 있기 때문에 O(NQ log N)이 됩니다. 이 값을 계산해보면 100억에 가까운 값으로, 1초에 연산을 1억~10억회를 하므로 제한시간내에 돌아가지 못합니다. 이 문제를 풀려면 어느 정도 사전 지식을 갖춰야 하고, 시간 복잡도에 대한 개념을 공부해보시면 좋을 것 같습니다.

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

문제

문제

출처

ICPC

7469 C언어 시간초과

youk6767 3년 전 0

leinad2 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말