sk251525   6년 전

예시 2개를 넣었을 때 맞았는데.. 또 다른 예시를 넣으면 틀린 것도 나와서 틀렸습니다..

뭘 수정해야할지 모르겠어요.. 알려주시면 감사하겠습니다.

idx = -1 로 한 것도 잘못된건가요??

idx =0 으로 해야하나...

chogahui05   6년 전

혹시 graph를 어떤 식으로 구축하셨는지 물어봐도 될까요?

그래프가

가장 왼쪽사대보다 왼쪽에 있는 경우는 쭉쭉 올라가는 함수고요.

가장 오른쪽 사대보다 우측에 있는 경우는 쭉쭉 내려가는 함수고요.


그 이외의 경우에는

사대가 L1, L2에 있다고 한다면

그 사이에 있는 Graph는 (L1, 사정거리)를 지나고, 기울기가 -1인 직선 (1)

(L2, 사정거리)를 지나고, 기울기가 1인 직선 (2)

이렇게 나누실 수 있는데요.


주의해야 할 건

(L1+L2)가 2로 떨어지지 않는 경우, 교점이 x.5로 나타날 수 있고요.

이거 부등식의 영역으로 푸시는 게 좋아요.

sk251525   6년 전

아래 코드처럼 짜봤습니다. 근데 이번엔 결과값이 안맞네요..

#include <bits/stdc++.h>
#include <stdlib.h>
int m,n,l;
int gun_x[100000+5], x, y, count_=0;
int sf(const void *a, const void *b){
    int aa = *(int *)a;
    int bb = *(int *)b;
    if(aa>bb) return 1;
    if(aa<bb) return -1;
    return 0;
}
int print(int tar_x){
    int st=1, ed=m, mid;
    int i;
    mid = (st+ed)/2;
    for(i=st;i<m;i++){
        if(st!=mid){
            if(x<gun_x[mid]) ed=mid;
            else if(x>gun_x[mid]) st=mid;
            else return gun_x[mid];
            mid=(st+ed)/2;
        }else{
            break;
        }
    }
    if(abs(gun_x[st]-x)>abs(gun_x[ed]-x)){
        return gun_x[ed];
    }else{
        return gun_x[st];
    }

}
int main(){
    int i;
    int dls;
    freopen("in.txt","r",stdin);
    scanf("%d %d %d",&m,&n,&l);
    for(i=0;i<m;i++){
        scanf("%d",&gun_x[i]);
    }
    qsort(gun_x,m,sizeof(gun_x[0]),sf);
    for(i=0;i<n;i++){
        scanf("%d %d",&x,&y);
    }
    for(i=0;i<n;i++){
        dls = abs(x-print(x))+y;
        if(dls<=l) count_++;
    }
    printf("%d\n",count_);
    return 0;
}

chogahui05   6년 전

좌표 0.5 = 1단위

좌표 1 = 2단위로 나눠보시는 건 어떠신가요?

sk251525   6년 전

이진검색으로는 풀었습니다. 근데, 그냥 이렇게  풀면 결과값이 다릅니다.

제 계산 상으로는 틀릴 점이 없는것 같은데;; 무엇이 틀렸나요??

#include <bits/stdc++.h>
#include <stdlib.h>
int sf(const void *a, const void *b){
    int aa = *(int *)a;
    int bb = *(int *)b;
    if(aa>bb) return 1;
    if(aa<bb) return -1;
    return 0;
}
int range(int gun_x, int x, int y, int l){
    int dls;
    dls = abs(gun_x-x)+y;
    //printf("dls : %d\n",dls);
    if(dls <= l){
        return 1;
    }else{
        return 0;
    }
}
int main(){
    int m,n,l;
    int gun_x[100000+5];
    int x[100000+5],y[100000+5];
    int count_=0;
    int i,j;
    int idx, tar_x, tar_y;
    freopen("in.txt","r",stdin);
    scanf("%d %d %d",&m,&n,&l);
    for(i=0;i<m;i++){
        scanf("%d",&gun_x[i]);
    }
    qsort(gun_x,m,sizeof(gun_x[0]),sf); ///사대 x좌표 오름차순 정렬

    for(i=0;i<n;i++){
        scanf("%d %d",&x[i],&y[i]);
    }
    qsort(x,n,sizeof(x[0]),sf); ///동물 x좌표 오름차순 정렬
    //qsort(y,n,sizeof(y[0]),sf); ///y좌표

    idx=0;
    for(i=0;i<n;i++){
        tar_x = x[i];
        tar_y = y[i];
        for(j=idx;j<m;j++){
            if(range(gun_x[j],tar_x,tar_y,l)){
                count_++;
                idx = j;
                break;
            }
            if(tar_x < gun_x[j]) break;
        }
    }
    printf("%d\n",count_);
    return 0;
}

chogahui05   6년 전

동물의 x좌표를 오름차순으로 정렬했군요.

만약에 이런 식으로 data가 들어오면 어떻게 될까요?

x좌표가 8이고, y좌표가 6인 동물이 있었나요? 데이터의 손실이 있습니다.

chogahui05   6년 전

ps. 혹시 2진 검색이면

동물의 x좌표를 보고 있을 법한 사대를 보는 건가요? 오히려 그게 더 쉬울 수도 있겠네요.. 생각해 보니..

sk251525   6년 전

데이터에 손실이 있다는 말을 이제 이해해서
구조체로 코드 몇개만 좀 바꿨더니 됐습니다... 계속해서 도움주셔서 감사합니다.

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