C언어 208제] 비토와 친척들(Vito's Family)

출처 : 반크_백제역사 유적지구와 이스탐블역사 유적지구

 

문제]

유명한 갱스터인 비토 데드스톤(Vito Deadstone)이 뉴욕으로 이사를 간다. 뉴욕에는 그의 가족들이 매우 많이 살고 있는데 그들은 모두 람피아 거리(Lamafia Avenue)에 살고 있다. 그는 그 친척들을 자주 만나러 갈 계획이기 때문에 친척들과 가까운 곳에 집을 구하기로 했다.
비토는 모든 친척집과의 거리 총합이 가장 작은 곳에 집을 구하고 싶어하는데, 하필이면 당신에게 그 문제를 해결하기 위한 프로그램을 만들어내라는 협박 편지를 보내왔다.

입력
입력은 여러 개의 테스트 케이스로 구성된다. 첫번째 줄에는 테스트 케이스의 개수가 들어있다.
각 테스트 케이스마다 친척집의 수를 나타내는 정수 r(0<r<500)과 각 친척짐의 번지수를 나타내는 정수 S1, S2, ..., Si, ..., Sr(0<Si<30000)이 입력된다. 친척 중에는 같은 번지에 살고 있는 사람들도 있다는 점에 주의하자.

출력
각 테스트 케이스에 대해 비토가 원하는 위치에 집을 구했을 경우에 

그 집으로부터 각 친천집까지의 거리의 총합을 출력해야 한다. 

번지 수가 Si와 Sj인 두 집 사이의 거리는 

 

로 구한다.

 

입력 예
2
2 2 4
3 2 4 6

출력 예
2
4



출처]
Programming Challenges 알고리즘 트레이닝 북(한빛미디어) : 문제 25 비토와 친척들(Vito's Family) p120

 

참고풀이]

#include <stdio.h>
#include <string.h>
                   
int main()
{
   int A[500]={0};
   int cases, N;
   int left, right, i, j;
   int pivot, tmp, Sum;

   //테스트 수 입력받는다. 
   scanf("%d",&cases);
   while(cases-- > 0)
   {
      scanf("%d",&N);
      for(i=0;i<N;i++) scanf("%d",&A[i]);

      left=0;
      right=N-1;
      do {
         pivot = A[left];
         i=left;
         j=right;
         while(i<=j)
         {
            while(i<=right && A[i]<=pivot) i++;
            while(j>left && A[j]>=pivot) j--;
            if(i < j)
            {
               tmp=A[i]; A[i]=A[j]; A[j]=tmp;
            }
         }
         A[left] = A[j];
         A[j]=pivot;
         if(j < N/2)
            left = j + 1;
         else
            right = j - 1;
      } while(j != N/2);

      Sum=0;
      for(i=0;i<j;i++) Sum += (pivot - A[i]);
      for(i=j+1; i<N; i++) Sum += (A[i] - pivot);

      printf("%d\n", Sum);
   }
   return 0;
}

 

참고풀이 결과]

 

 

 

 

 

대한민국의 아름다운 영토, 독도의 겨울