int set[1000000] = {0, };

 

K2 = K + 1;
  K = K - 1;

 

  for (i = 0; i < S; i++)
  {
   fscanf(fp, "%d", &set[i]);
  }

 

  qsort(set, S, sizeof(int), COMPARE);

 

  while (1)
  {
   ++K;
   --K2;

 

   for (i = 0; i < S; i++)
   {
    for (j = i + 1; j < S; j++)
    {
     if ((set[i] + set[j]) == K || (set[i] + set[j]) == K2)
     {
      count++;
     }
    }
   }

 

   if (count != 0)
   {
    printf("%d\n", count);
    break;
   }
  }

 

 

일단 무슨 문제인지 설명드리자면,

 

어떤 특정 수열이 주어집니다 (ex. 1 7 3 5)

 

이 특정 수열들 중 2개 수의 합으로 (이외 조건은 없습니다 무조건 2개 수의 합!)

 

주어진 K와 같은 숫자가 나오는 횟수를 검사하는 알고리즘인데요.

 

가령이면 1 7 3 5 수열이 주어지고

 

K = 20이면

 

1 7 3 5 중 어떤 2개수의 합으로도 20을 만들 수 없기 때문에

근사치로 값을 증감시키면서 그 값이 있는지 탐색해야 합니다.

 

 

위 알고리즘으로 구현하려 했던 것은

 

우선 주어진 수열을 정렬시킨 다음 (1 7 3 5를 기준으로 하면 1 3 5 7로 정렬)

 

1을 피봇으로 잡고 +3, +5, +7 수행.. 3을 피봇잡고 +5, +7 수행.. 5를 피봇잡고 +7 수행.. (이 과정에서 K와 동일한 값이 있으면

카운트 증가)

 

반복문이 끝난 이후 카운트가 증가하지 않았다는 것은 근사치를 찾아야 한다는 의미 이므로

 

K를 2개의 근사치로 (K는 증가 근사치, K2는 감소 근사치) 나눠서 이 두개를 동시에 똑같이 탐색하는 알고리즘인데요..

 

 

 

저 위 알고리즘으로도 옳은 답은 다 나오는데 문제는 시간이 너무 오래걸려서 문제 제출이 안되네요.. 시간이 엄청 초과된 듯 합니다 ㅠㅠ

 

아무래도 이중포문으로 시작한 탐색이 엄~청 오래걸리는 모양인데,

 

여기서 시간을 줄일 방법이 제 머리로는 생각이 나지 않습니다. 혹시 도움을 구해도 될까요 ㅠ.ㅠ