[Algorithm][C언어] 백준 4307번: 개미

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

4307번: 개미

 

문제

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

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

 

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 막대의 길이와 개미의 수 n이 주어진다. 다음 n개 줄에는 숫자가 하나씩 주어지며, 이 숫자는 개미의 초기 위치를 나타낸다. 입력으로 주어지는 모든 수는 1,000,000보다 작거나 같으며, 공백으로 구분되어져 있다. 개미의 위치는 막대 왼쪽 끝에서부터 떨어진 거리이다.

 

출력

각 테스트 케이스에 대해서, 두 숫자를 출력한다. 첫 번째 숫자는 개미가 모두 땅으로 떨어지는 가능한 시간 중 가장 빠른 시간, 두 번째 숫자는 가장 늦은 시간이다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
        
int L, N;
        
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
        
    for (int t = 0; t < T; t++)
    {
     	cin >> L >> N;
        
        int minTime = 0, maxTime = 0;
        
        for (int i = 0; i < N; i++)
        {
        	int ant;
        	cin >> ant;
        
        	int antMin = min(ant, L - ant);
        	int antMax = max(ant, L - ant);
        
           	minTime = max(minTime, antMin);
     		maxTime = max(maxTime, antMax);
        }
        cout << minTime << " " << maxTime << "\n";
      }
      return 0;
}

코드 출처: https://jaimemin.tistory.com/1178

 

첨부한 티스토리 링크의 첫 문장처럼 "두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다."라는 문구 때문에 애를 먹어 결국엔 구글링을 한 문제이다. 두 개미가 만나는 상황을 자꾸 고려하게 되어 문제가 진행되지 않았는데, 구글링을 하고 나서야 이건 고려할 필요 없고 그저 그리디 문제일 뿐이라는 것을 알 수 있었다.