개미( BOJ 2136 )

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

2136번: 개미

 

문제 파악하기

길이가 L인 막대기 위에 있는 N마리의 개미 중 가장 늦게 떨어지는 개미의 번호와 시간을 구하는 문제입니다. N마리의 개미는 왼쪽 또는 오른쪽 방향으로 움직이며 서로 만나면 반대 방향으로 이동합니다. 개미들이 부딪히는 모든 경우를 시뮬레이션하는 방법을 가장 먼저 떠올릴 수 있지만 개미가 많아질수록 구현도 어려워지고 시간 복잡도 역시 증가합니다. 그렇다면 어떤 방법을 사용할 수 있을까요? 이 문제는 규칙을 찾으면 어렵지 않게 해결할 수 있습니다.

 

문제 해결하기

문제의 규칙은 여러 경우를 직접 그려보면 찾을 수 있습니다. 문제를 쉽게 확인하기 위해 길이가 6인 막대기 위의 개미가 5마리 있다고 가정하고 살펴보겠습니다.

 

(1) 개미가 모두 오른쪽으로 이동하는 경우 ( Ex. 1 2 3 4 5 )

- 모든 개미는 오른쪽으로 떨어지며, 모든 개미가 각각 (6 - 시작위치)초가 걸림

 

(2) 한 마리를 제외한 모든 개미가 오른쪽으로 이동하는 경우 ( Ex. 1 2 -3 4 5 )

- 가장 왼쪽의 개미는 왼쪽으로 떨어지며, 3초의 시간이 걸림

- 나머지는 오른쪽으로 떨어지며 왼쪽에서 2번째 개미부터 순서대로 4초, 3초, 2초, 1초의 시간이 걸림

 

(3) 두 마리를 제외한 모든 개미가 오른쪽으로 이동하는 경우 ( Ex. 1 -2 3 -4 5 )

- 왼쪽에서 2마리의 개미가 왼쪽으로 떨어지며 각각 2초, 4초의 시간이 걸림

- 나머지는 오른쪽으로 떨어지며 왼쪽에서 3번째 개미부터 순서대로 5초, 3초, 1초의 시간이 걸림

 

(4) 세 마리를 제외한 모든 개미가 오른쪽으로 이동하는 경우 ( Ex. 1 -2 -3 4 -5 )

- 왼쪽에서 3마리의 개미가 왼쪽으로 떨어지며 각각 2초, 3초, 5초의 시간이 걸림

- 나머지는 오른쪽으로 떨어지며 왼쪽에서 4번째 개미부터 순서대로 5초, 2초의 시간이 걸림

 

모든 경우를 확인할 수도 있지만 여기까지 확인해도 규칙을 찾는데 큰 무리가 없을 것으로 보입니다. 우리는 각각의 개미들이 떨어지는 위치가 왼쪽 방향(음수)으로 이동하는 개미의 마릿수에 의해 결정된다는 규칙을 발견할 수 있으며, 이를 통해 떨어지는 시간 역시 파악할 수 있습니다. 수직선 위에서 움직이기 때문에 왼쪽으로 이동하는 개미들의 수만큼 개미들은 왼쪽으로 떨어지며, 가장 왼쪽의 개미부터 순서대로 왼쪽 방향으로 떨어지게 됩니다. 그리고 나머지 개미들은 오른쪽으로 떨어지게 됩니다.

 

그럼 개미들이 떨어지는 시간은 어떻게 알 수 있을까요? 바로 개미들이 떨어지는 위치와 이동 방향으로 구할 수 있습니다. 왼쪽으로 떨어지는 개미들은 왼쪽으로 이동한 개미들의 위치에 영향을 받습니다. 개미들이 부딪히는 순간 반대 방향으로 이동하는 과정을 통과한다고 생각하면 이해하기 편합니다. 만약 개미들이 통과한다면 왼쪽으로 떨어지는 개미들은 왼쪽으로 이동하는 개미들의 위치에 따라 왼쪽부터 순서대로 떨어지게 됩니다. 반대로 오른쪽으로 떨어지는 개미 역시 반대로 오른쪽으로 이동하는 개미들의 위치에 영향을 받으며, 이를 활용하면 어렵지 않게 개미들이 떨어지는 시간을 구할 수 있습니다. 개미들이 떨어지는 방향을 참고해서 왼쪽의 개미부터 순서대로 매칭하면 떨어지는 시간을 구할 수 있으며, 구한 시간 중 최댓값을 구하면 문제를 해결할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <utility>
#include <algorithm>
#define NMAX 100010
using namespace std;
typedef pair<int, int> PAIR;
 
int N, L;
PAIR inp[NMAX];
 
int cntL, l, r;
PAIR ret[NMAX];
 
int abs(int k) { return k>0 ? k:-k; }
bool cmp(PAIR a, PAIR b) { return abs(a.first) < abs(b.first); }
 
int main() {
    // 입력
    scanf("%d %d", &N, &L);
    for(int i=0;i<N;i++) {
        scanf("%d", &inp[i].first);
        inp[i].second = i+1;
 
        // 오른쪽 방향의 개미 개수 세기
        if(inp[i].first < 0) cntL++;
    }
 
    // 개미의 위치를 기준으로 정렬
    sort(inp, inp+N, cmp);
 
    l = r = 0;
    for(int i=0;i<N;i++) {
        // 오른쪽 방향의 개미만큼 왼쪽으로 떨어짐
        // 왼쪽에 떨어지는 개미의 이동 거리 : 가장 가까운 위치에 있는 오른쪽 방향 개미의 이동거리
        // 오른쪽에 떨어지는 개미의 이동 거리 : 가장 가까운 위치에 있는 왼쪽 방향 개미의 이동거리
        if(i < cntL) {
            while(inp[l].first > 0) l++;
 
            ret[i] = {-inp[l++].first, inp[i].second};
        }
        else {
            while(inp[r].first < 0) r++;
            ret[i] = {L-inp[r++].first, inp[i].second};
        }
 
    }
 
    // 이동거리 기준으로 정렬
    sort(ret, ret+N);
 
    // 출력
    printf("%d %d", ret[N-1].second, ret[N-1].first);
}

후기

막대기 위에서 움직이는 개미에 관한 여러 문제가 있는데 이 문제를 풀어보면 나머지 문제는 모두 어렵지 않게 해결할 수 있다고 생각합니다. 재미있는 애드훅 문제여서 많은 사람들에게 추천하고 싶은 문제입니다.