백준(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;
}
