글 읽기 - c언어 질문

hoon3722 3년 전 0

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

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

아 그리고 cd에 같은 수로 꽉 차있으면 한번 찾을때마다 계속 돌아야되서 data라는 배열을 따로 만들고 거기다가 값을 저장해놓아서 반복 안하게 했습니다.

50퍼쯤에서 틀렸습니다 뜹니다.

왜 틀렸는지 보니까 이게 뜨네요

제 생각에는 clon 함수에서 아무리 생각해도 빈틈이 없는것같은데..

(정렬에는 문제가 없고 이분탐색함수 clon이나 find 함수에 문제가 있습니다.)

Main.c: In function ‘clon’:
Main.c:63:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

#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 *data, int n){
    int True=1;
    if(cd[0]>key || cd[n]<key)return 0;
    int index;
    
    if(key==cd[n])index=n;
    else index=clon(key,cd,0,n);
    
    if(  index == -1 ) return 0;
    if(data[index]>0)return data[index];
    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++;
        }
        data[index]=True;
    }
    
    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 *data=NULL;
    data=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];
            data[cdi]=0;
            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,data,(n*n)-1); 
    }
    
    printf("%d",count);
    
    return 0;
}

3587jjh 3년 전 0

다른 질문글을 읽어보시는걸 추천드립니다

yj10516 3년 전 0

이게 WA로 연결되는건 아니지만 무한루프 가능성이 있어서

n=1 인 Input이 왔을때 clon이 start=end=0 인 상태로 호출할 수 있습니다.

이경우에 clon 이 무한루프상태에 빠질 수 있어서 문제가 될 것 같습니다.

yj10516 3년 전 1

int 형으로 답을 저장하셨는데

모든 A[i]=B[i]=C[i]=D[i]=0 일때의 답은 n^4로

n=4000일때 Int로 저장시 오버플로우가 납니다.

hoon3722 3년 전 1

참고했더니 풀었습니다. 감사합니다.

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

문제

문제

출처

ICPC

c언어 질문

hoon3722 3년 전 0

3587jjh 3년 전 0

yj10516 3년 전 0

yj10516 3년 전 1

hoon3722 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말