백준(BOJ) 4307번 개미

문제 : https://www.acmicpc.net/problem/4307

문제

개미 여러 마리가 길이가 lcm인 막대 위에 있다. 각 개미의 이동 속도는 모두 일정하며, 1cm/s이다. 개미가 막대의 마지막까지 걸어간다면, 개미는 그 즉시 떨어지게 된다. 또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다.

가장 처음에 막대 상에서 개미의 위치를 알고 있다. 하지만, 개미가 어느 방향으로 움직이는 지는 알 수가 없다. 이때, 모든 개미가 땅으로 떨어질 때까지 가능한 시간 중 가장 빠른 시간과 느린 시간을 구하는 프로그램을 작성하시오.

풀이 :

개미가 만나게 되면 방향을 반대로 바꾸는 것과는 상관없이 모든 개미가 떨어질때 가장 빠른 시간은 출발선 or 도착선으로 가장 빠르게 

떨어지는 개미 중 가장 오래걸리는 값을, 가장 느린 시간은 출발선 or 도착선으로 가장 오래 걸리는 개미들 중 가장 느린 값을 골라 

주면 된다.

코드 ( C++ )

#include <iostream>

#include <queue>

using namespace std;

int stick, n;

int main()

{

int C;

cin >> C;

while (C--)

{

cin >> stick >> n;

int fast = 0, late = 0;

for (int i = 0; i < n; ++i)

{

int loc;

cin >> loc;

int antFast = min(loc, stick - loc);

int antLate = max(loc, stick - loc);

// 가장 빠른 개미들 값 중 가장 큰 값

fast = max(fast, antFast);

// 가장 느린 개미들 값 중 가장 큰 값

late = max(late, antLate);

}

cout << fast << " " << late << "\n";

}

return 0;

}