글 읽기 - 이분탐색 시간초과 질문입니다

formejyj 6년 전 0

왜 자꾸 시간초과가 나는지 모르겠습니다ㅠㅠ

통과한 답과 비교도 해봤는데 왜 이 코드가 타임오버인지도 모르겠어요ㅠㅠ

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

long long sum(long long* arr , long long pos, long long n)
{
  long long  i,total=0;
  for(i=0; i<=n; i++)
  {
    if(arr[i]-pos>0)
    total = total+(arr[i]-pos);
  }
  return total;
}

int main()
{
  int i;
  long long n,m;
  long long *arr;
  long long total=0,max=0,min=0,half;

  scanf("%lld %lld" ,  &n, &m);
  arr=(long long*)malloc(sizeof(long long)*n);

  for(i=0; i<n; i++)
  {
    scanf("%lld" , &arr[i]);
    if(arr[i]>max)
    max = arr[i];
  }
//===========여기서 부터 뭔가 다른것 같습니다. 윗부분은 다른 Accpet 코드와 같고
//밑에도 거의 비슷한데 왜 시간초과일까요ㅠ
  half = max/2;

  while(1)
  {
    total = sum(arr,half,n);
    if(total==m)
      break;
    if(sum(arr,half,n)>m)
    {
      if(sum(arr,half+1,n)<m)
        break;
      else
        {
          min = half+1;
          half = (min+max)/2;
        }
    }
    else
    {
      max = half-1;
      half = (min+max)/2;
    }
  }

  free(arr);
  printf("%lld" , half);
  return 0;
}

hun222y 6년 전 0

while문 안에서 total = sum(arr,half,n); 이렇게 하신다음 if문내에도 계속적으로 sum함수를 호출하기 때문이 아닐까요?

total = sum(arr,half,n); 라고 하셨으면 그냥 total로서 if문내에서 비교를 하셔도 될꺼같은데 ..

formejyj 6년 전 0

@fkdlslss 다른코드로 고쳐서 AC받았다가 원래로 고쳐봤는데 갑자기 AC뜨네요 ㅋㅋㅋㅋ

뭐가 뭔지..ㅋㅋㅋ 댓글 감사드립니다!!

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

문제

문제

출처

ICPC

이분탐색 시간초과 질문입니다

formejyj 6년 전 0

hun222y 6년 전 0

formejyj 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말