백준#2399 거리의 합

https://www.acmicpc.net/problem/2399

2399번: 거리의 합

정렬 문제로 분류된 거리의 합 입니다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace _2399
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = int.Parse(Console.ReadLine());
            var numList = Console.ReadLine().Split(' ')
                .Select(x => ulong.Parse(x)).OrderBy(x => x).ToList();
 
            ulong ans = 0;
            for(int i = 0; i < count / 2; i++)
            {
                int mult = numList.Count - (i * 2) - 1;
                ulong targetNum = numList[numList.Count - i - 1] - numList[0 + i];
                ans += targetNum * (ulong)mult;
            }
 
            Console.WriteLine(ans * 2);
        }
    }
}
 

풀이

ex) 5

3 2 4 1 5

 

이걸 정렬하면 일직선상에 1, 2, 3, 4, 5 이런식으로 나오며

1과 2사이, 2와 3사이, 3과 4사이, 4와 5사이 이런식으로 4개의 구간이 나옵니다.

 

n^2번 돌려 모든 점사이의 거리를 구할 수도 있겠지만 1만개의 갯수를 돌리면 시간 초과가

날수도 있겠다는 생각이 들었습니다.

 

가장 왼쪽과 가장 마지막 (1과 5) 사이의 거리를 보면 특이한 점이 하나 있습니다.

 

1 ~ 5는 1~2, 2~3, 3~4, 4~5 사이의 거리를 합한것과 같습니다.

또한 1~3, 3~4, 4~5 사이의 거리르 합한 것과도 같습니다.

 

이를 행렬로 표현 했습니다.

   1  2  3  4  5

1 0  1  2  3  4

2 1  0  1  2  3

3 2  1  0  1  2

4 3  2  1  0  1

5 4  3  2  1  0

 

이런 식으로 나오게 되는데 [1, 2]는 1과 2사이의 거리 입니다.

 

1부터 5사이의 거리를 한번 구하면 [1,2], [2,5]의 합이 구해집니다.

두번 구하면 [1,3], [3, 5]가 구해지며 세번 구하면 [1,4], [4,5]

다섯번 하게 될 시 [1,5]가 구해집니다.

 

마찬 가지로 2 ~ 4의 거리또한 [2,3], [3, 4]가 한번, [2,4]가 한번 구해집니다.

 

이것을 O(n)시간 하여 최종답을 구했습니다.