10255번 교차점

Problem link: https://www.acmicpc.net/problem/4307

Keywords: Programming Contest Challenging

그냥 블로그를 너무 업데이트하지 않고 있는 것 같아서, 죄책감에 아무거나 쉬운 것을 하나 골라 잡고 풀었다. 학부 1학년 떄인가 구매했었던 소위 노란책에 있는 문제들을 모아놓은 백준 저지 문제집이 있더라. 간간히 머리 식힐 겸 풀어야겠다.

일단, 가장 짧은 시간을 구하는 방법을 생각해보자. 이 경우는 굉장히 쉽게 답을 찾을 수 있는데, 모든 개미들이 각자 자신에게 더 가까운 끝 점 (오른쪽 또는 왼쪽) 을 향해 움직여주면 된다. 이 때는 개미들이 이동중에 서로 만나는 경우가 존재할 수 없는데, 아래 그림(?) 을 보면 이해할 수 있다.

-------------
   ^ 
   A

처음에 위와 같이 개미 A가 있었다고 해보자, 그리고 이 개미는 왼쪽 끝이 더 가깝기 때문에 왼쪽으로 이동시킬 것이다. 초기 위치가 이 개미보다 왼쪽에 있었던 개미들은 자명하게 왼쪽 끝으로 이동할 것이고 (오른쪽 끝이 더 까까울리가 없으므로), 따라서 개미 A와 이동 중에 만나지 않는다. 초기 위치가 이 개미보다 오른쪽에 있었던 개미들은 오른쪽 또는 왼쪽으로 이동할 수 있을텐데, (1)이들 중 오른쪽으로 이동하는 개미는 당연히 A와 만날 수 없고, (2)왼쪽으로 이동하는 개미도 모두 속력이 같기 때문에 A를 만날 수 없다. 요약하면, 가장 짧은 시간은 아래와 같이 구할 수 있다.

두번째로, 가장 긴 시간을 구하는 방법을 생각해보자. 이때는 개미가 서로 마주치면 방향을 바꾼다는 조건이 있어서 괜히 사람을 헷갈리게 만드는데, 사실 이 조건은 없다고 생각해도 아무 문제가 없고, 이것을 떠올리는게 솔루션의 핵심이다.

-------------
   ^^ 
   AB
   ><

이동 중에 개미 A, B가 위와 같이 위치했다고 해보자. 이때, A는 오른쪽으로, B는 왼쪽으로 이동 중이다.

-------------
   ^^ 
   AB
   <>

정획히 1초 후에 두 개미는 만나고, 방향을 바꾸어서 다시 위와 같이 위치하게 될 것이다. 단지, 이때는 A는 왼쪽으로, B는 오른쪽으로 이동 중이다.

-------------
   ^^ 
   BA
   <>

우리는 각 개미의 이름 따위는 신경쓰지 않으므로 이 경우는 개미 A, B를 서로 바꾸어서 위와 같이 표현해도 완벽하게 동일하다. 위의 그림은 무엇을 나타내는가? 개미들이 마주쳐도 방향을 바꾸지 않는 경우를 의미한다. 이렇게 생각하면 모든 개미들이 그냥 독립적으로 움직인다고 생각할 수 있고, 따라서 모든 개미들이 각자 자신에게 더 먼 끝 점을 향해 움직이는 경우를 헤아려주면 된다. 굳이 식으로 표현해주면 아래 정도가 되리라.

아래는 솔루션이다.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int TC;
int L, N;

int main(void) {
  // For faster IO.
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  cin >> TC;
  while (TC--) {
    int shortest = 0;
    int longest = 0;
    cin >> L >> N;
    while (N--) {
      int pos;
      cin >> pos;
      shortest = max(shortest, min(pos, L - pos));
      longest = max(longest, max(pos, L - pos));
    }
    cout << shortest << ' ' << longest << '\n';
  }

  return 0;
}