글 읽기 - 반례가 혹시 있을까요..?

khj0426 2년 전 0

안녕하세요 ! 혹시 제가 푼 코드에 대해 반례가 있는지 궁금합니다 . 70프로까지 가다가 틀려서 어느 부분이 잘못된건지 모르겠어요..부탁드립니다..!

#include <stdio.h>
#include <stdlib.h>
 
struct birth{ //생일 선물 구조체
    long long price; //생일선물가격
    long long value; //생일선물 가치
};
 
int compare(const void *a,const void *b){ //생일선물 가격에 대해서 오름차순 정렬
    struct birth num1 = *(struct birth *)a;
    struct birth num2 = *(struct birth *)b;
    if(num1.price < num2.price){
        return -1;
    }
    else if(num1.price > num2.price){
        return 1;
    }
    else{
        return 0;
    }
}
 
int main(void){
    int n; 
    long long d;
    
    struct birth arr[100000];
    scanf("%d %lld",&n,&d);
 
    for(int i = 0;i<n;i++){
        scanf("%lld %lld",&arr[i].price,&arr[i].value); //생일선물 가격 ,가치 입력받고
    }
 
    qsort(arr,n,sizeof(struct birth),compare);//생일선물 가격에 대해서 오름차순 정렬
                 
    long long l = 0; //투포인터 왼쪽
    long long r = 0; //오른쪽
    long long max = -1; //생일선물 가치의 최대값 초기화
    long long sum = 0; //생일선물 가치의 합
    
    while(l<=r && r<=n){
        
         if(sum > max){ //sum값이 max보다 크다면 갱신
            max = sum;
        }
        
        if(abs(arr[r].price - arr[l].price) < d){ //생일선물 가격 차이가 d보다 작을떄
            r++; 
            sum = sum + arr[r].value;
        }
        else{ //생일선물 가격 차이가 d보다 크거나 같을떄
            sum = sum - arr[l].value;
            l++;
        }
       
 
    }
    if(n!= 1){
     printf("%lld\n",max);
    }
    else if(n == 1){ //n이 1일떄 d -> 0이니깐 하나있는 생일선물의 값 출력
        printf("%lld",arr[0].value);
    }
}

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

문제

문제

출처

ICPC

반례가 혹시 있을까요..?

khj0426 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말