C언어 184제] 2005년 1월 USACO Contest Silver 3번 거리의 합

출처 : 반크_세계유산 경복궁

 

문제]

수직선에 n개의 점이 찍혀 있다. 각각의 점의 x좌표가 주어졌을 때, n2개의 모든 쌍에 대해서 거리를 더한 값을 구하는 프로그램을 작성하시오.

즉, 모든 i, j에 대해서 |x[i] - x[j]|의 합을 구하는 것이다.

입력
첫째 줄에 n(1 ≤ n ≤ 10,000)이 주어진다. 다음 줄에는 x[1], x[2], x[3], …, x[n]이 주어진다. 각각은 0 이상 1,000,000,000 이하의 정수이다.

출력
첫째 줄에 답을 출력한다.

예제 입력 1 
5
1 5 3 2 4

예제 출력 1 
40


출처 : 백준_2399번

 

참고풀이]

#include <stdio.h>
#include <stdlib.h> //malloc(), free()

int main()
{
   int i,j;//인덱스 또는 반복변수
   long long int Sum;//합변수 
 
   //점 수 N개를 입력받는다.
   int N;
   scanf("%d",&N);
   if(N>=1 && N<=10000)
   {
      //점 N개를 입력받기 위하여 동적메모리를 선언한다. 
      long long int *X=(long long int *)malloc(sizeof(long long int)*N);
      //선언된 배열에 자료를 입력받는다.
      for(i=0;i<N;i++) 
      {
         scanf("%d",&X[i]);
         if(X[i]>=0 && X[i]<=1000000000) continue;
         else return 0;
      }

      //각 점의 |X[i]-X[j]|의 합을 구한다. 
      Sum=0;
      for(i=0;i<N;i++)
      {
         for(j=0;j<N;j++)
            Sum+=(X[i]-X[j]>=0) ? X[i]-X[j] : -1*(X[i]-X[j]);
      }

      //결과출력
      printf("%lld",Sum);

      //선언된 동적메모리를 해제한다. 
      free(X);
   }

   return 0;
}

 

참고풀이 결과]

 

 

 

 

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