BOJ 5054 - 주차의 신

문제

일직선 도로에 있는 여러 가게를 모두 방문하고 시작 위치로 돌아올 때, 최소 이동 거리를 구하라.

입력

테스트 케이스 수 T, 각 케이스마다 가게 수 N과 N개의 위치가 주어진다.

출력

각 테스트 케이스마다 최소 이동 거리를 출력한다.

예제

입력	출력
`1` `3` `2 1 3`	`4`

풀이

최소 이동 거리는 가장 왼쪽과 오른쪽 가게 사이 거리의 2배이다.

입력에서 최솟값(MIN)과 최댓값(MAX)을 구한다
2 * (MAX - MIN)을 계산하여 출력한다

핵심 아이디어: 시작 위치에 관계없이, 모든 가게를 왕복하는 최소 거리는 양 끝 사이 거리의 2배이다.

코드

#include <iostream>
 
using namespace std;
 
int main()
{
  int T;
 
  cin >> T;
 
  for (int i = 0; i < T; i++)
  {
    int n;
    int arr[20];
    int sum = 0;
    int space;
    int MIN = 100, MAX = 0;
    cin >> n;
    for (int j = 0; j < n; j++)
    {
      cin >> arr[j];
      sum += arr[j];
      if (MIN > arr[j])
        MIN = arr[j];
      if (MAX < arr[j])
        MAX = arr[j];
    }
    space = sum / n;
 
    int result = 2 * (MAX - space) + 2 * (space - MIN);
 
    cout << result << "\n";
  }
}

복잡도

시간: O(T * N) (T: 테스트 케이스 수, N: 가게 수)
공간: O(N)

문제