백준 #4307 개미

BOJ #4307 - 개미

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

# 문제 분류

상상력

풀이 접근 방법

모든 개미들의 이동경로를 알아봐야한다면, 개미가 부딪힐 때를 모두 계산해야하므로 정말 복잡해질 것이다.
그러나 개미들을 구분짓지 않는다면? 개미가 부딪혀 돌아가는 것을 그저 통과하는 것으로 볼 수 있다.
따라서 막대의 중간에서 가장 가까이 있는 개미가 끝을 향해 달리는 최단시간이 최소 시간이고,
막대의 양 끝단에서 가장 가까이 있는 개미가 반대편 끝을 향해 달리는 시간이 최대 시간이다.

최소와 최대 모두 막대의 가운데를 기준으로 가장 가까이 있는 개미와 가장 멀리 있는 개미를 비교하는 식으로 작성했다.
단순히 개미가 왼쪽일지 오른쪽일지에 대한 모든 경우를 조사하는 것 부터도 $O(2^n)$ 이기 때문에 절대 불가능하고,
위의 알고리즘을 떠올리면 개미들의 위치만 조사하면 되므로 $O(n)$ 만에 해결 가능하다.

소스 코드

#include <iostream>
#include <cmath>

using namespace std;

int n, m, k;

void ant(int len, int siz, int arr[1000010]){
    int minn = 10000000;
    float maxx = float(len)/2;
    for(int i=0; i<siz; i++){
        if(abs(float(len)/2 - minn) > abs(float(len)/2 - arr[i])) minn = arr[i];
        if(abs(float(len)/2 - maxx) < abs(float(len)/2 - arr[i])) maxx = arr[i];
    }

    cout << min(minn, len-minn) << " " << max(maxx, len-maxx) << endl;
}

int main(){
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> m >> k;
        int arr[1000010] = {0};
        for(int j=0; j<k; j++) cin >> arr[j];
        ant(m, k, arr);
    }

    return 0;
}