글 읽기 - c언어 질문

hoon3722 3년 전 0

40퍼 쯤에서 시간 초과뜨네요.

제가 푼 방법은 a,b,c,d 4개를 두개로 나누어서 두개씩 짝을 지어서 만든 합의 배열을 만들었습니다. ( ab의 합 배열, cd의 합 배열)

그 다음에 cd 배열을 병합정렬로 정렬시키고 cd배열을 이분 탐색해서 하나씩 ab배열의 원소와 cd배열의 원소 합이 0이되는걸 세도록 했습니다.

도대체 왜 시간초과가 뜨는지 모르겠습니다. 문제에 있는 예제도 작동이 되는데..

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

void part(int *nums, int *buf, int start, int end){
    int m=(start+end)/2;
    int l=start;
    int r=m+1;
    int k=start;
    
    while(l<=m && r<=end){
        
        if(nums[l]<nums[r]){
            buf[k]=nums[l];
            l++;
        }
        else{
            buf[k]=nums[r];
            r++;
        }
        k++;
    }
    if(r>end){
        while(l<=m){
            buf[k]=nums[l];
            l++;
            k++;
        }
    }
    else{
        while(r<=end){
            buf[k]=nums[r];
            r++;
            k++;
        }
    }
    for(int i=start;i<=end;i++){
        nums[i]=buf[i];
    }
}

void whole(int *nums, int *buf, int start, int end){
    int mid=(start+end)/2;
    if(start<end){
        whole(nums,buf,start,mid);
        whole(nums,buf,mid+1,end);
        part(nums,buf,start,end);
    }
}

int* sort_cd(int* nums, int size){
    int *buf=NULL;
    buf=malloc(sizeof(int)*size);
    whole(nums,buf,0,size-1);
    return buf;
}

int clon(int key,int *cd, int start, int end){
    int mid=(start+end)/2;
    if(cd[mid]==key)return mid;
    if(end-start==1)return -1;
    if(cd[mid]<key)return clon(key,cd,mid,end);
    if(cd[mid]>key)return clon(key,cd,start,mid);
}

int find(int key, int* cd, int n){
    int True=1;
    if(cd[0]>key || cd[n]<key)return 0;
    int index;
    index=clon(key,cd,0,n);
    if(  index == -1 ) return 0;
    else{
        int left=index-1;
        int right=index+1;
        while(left>=0 && cd[left]==key){
            True++;
            left--;
        }
        while(right<=n && cd[right]==key){
            True++;
            right++;
        }
    }
    return True;
}

int main()
{
    
    int n,i,t;
    int a[4002];
    int b[4002];
    int c[4002];
    int d[4002];

    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
    }
    
    int *ab=NULL;
    ab=malloc(sizeof(int)*n*n);
    
    int abi=0;
    for(i=0;i<n;i++){
        for(int t=0;t<n;t++){
            ab[abi]=a[i]+b[t];
            abi++;
        }
    }
    
    int *cd=NULL;
    cd=malloc(sizeof(int)*n*n);
    int cdi=0;
    for(i=0;i<n;i++){
        for(t=0;t<n;t++){
            cd[cdi]=c[i]+d[t];
            cdi++;
        }
    }
    
    int *changed_cd=NULL;
    changed_cd=sort_cd(cd,n*n);
    
    int count=0;
    
    for(i=0;i<n*n;i++){
        count+=find((-1)*ab[i],changed_cd,n*n-1); 
    }
    
    printf("%d",count);
    
    return 0;
}

yj10516 3년 전 1

만약 모든 a[i]=b[i]=c[i]=d[i]=0 이라면

위 코드는 binary search 당 n^2번의 연산을 하게 되어서

O(n^4) 가 됩니다.

hoon3722 3년 전 1

정확한 지적 감사합니다. 코드 길어서 찾기도 힘들었을텐데,,

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

문제

문제

출처

ICPC

c언어 질문

hoon3722 3년 전 0

yj10516 3년 전 1

hoon3722 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말